||Getting the Video out of Your New iPod--for Cheap!|
I tried this and hard video problems myself. Audio was fine, but the video was garbled. I tried to play the video through iTunes to make sure it worked, and guess what-- it didn't. The program I used encoded it to mpeg4, but I guess it has to be a special type of mpeg4 for iPods.
So I searched and found GP3, and now my test video works, on iTunes and through the tele. I'm not sure if it's just me, but the quality does seem a little bit lower, but not by much.
Use google, and you should find a helpful thread with a tutorial on how to use it also.