I have found that some videos play with video and others don't. To account for this, I use mencoder to resize them to the screen size (to save space as well as resources) and re-encode them so that every video works. I usually just run the encoder with the device as the target, so it writes the file directly where I want it.
The command I use is this:
"C:\Program Files\mplayer\mencoder.exe" %1 -o %2 -vf scale=480:-2 -of avi -ovc lavc -oac mp3lame -lavcopts vcodec=mpeg4 -lameopts abr:br=128
Where %1 is the input file and %2 is the output file (Make sure to put quotes around them if there are spaces in the path or filename). Of course, you have to download mencoder (part of mplayer) which can be found here: Entering MPlayer homepage
This command automatically scales it to the WIDTH of 480, not taking into account the height, but maintaining the aspect ratio.
Hope this helps!