Well, I'm no iPod expert cause I don't have one but I think your problem might be your iTunes converter. I think this is an iPod Converter and a good one, check it out. Here's the link:

http://www.videora.com/en-us/Converter/iPod/

I think it's Windows only though.

If you want a different one, search iPod Video Converters in Google and you'll find tons.

Hope this solves your problem.

EDIT: Damn didn't know you had to pay for this...Search google and you'll find some free converters that are good.