No picture when playing video with MediaPlayer in Android

I recently had a problem where I could get an mp4 file to play, but when I demo'ed my application in the Android Virtual Device (AVD) i would only hear audio, no video.

I thought I'd better rule out the video itsself as being faulty, and after a quick hunt around on google, I found a guy directing me to this website:

http://www.law.duke.edu/cspd/contest/finalists/

The Video "Documentaries and Me" worked perfectly in my AVD with MediaPlayer, and allowed me to view the video.

I tried quickly encoding my own .mp4 files using VideoLAN but they didn't work either, so it would be interesting to know what sort of encoding settings we should be looking at and what program we should use to get mp4 files in the correct spec for the Android MediaPlayer