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:

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