It's hard to troubleshoot this problem without knowing how you converted the video. If you're on a Mac, try this free program that makes it very easy to convert video for iPod:
http://www.isquint.org/

If you're on a PC, try searching for "iPod video" on download.com, and then you can filter the search for Windows XP and free software.