monkey me (and others who have stumbled to this same problem),
As far as I can tell, the problem is the iTunes built-in converter. The solution I found is using MP4 converters to do the trick.
Mac users: HandBrake and PEnGUIn Encoder work just fine (And, dolhpins217, I think HandBrake supports .avi files, so there's the answer for your first question.). Both have iPod presets, so it's pretty easy to use. Ah... PEnGUIn allows you to select as many files you want to convert (HandBrake converts on file at a time, you have to wait and add another), since video converting takes pretty long It's a good thing, you can just let it working overnight.
Windows users: There's is a version of HandBrake for you, but I can't say if it's good. You could search another one... I googled "MP4 converter pc", this on seems ok:
4U MP4 Converter
(
http://www.mp4-converter.biz/)
Hope I could help