As documented under
http://developer.android.com/guide/appendix/media-formats.html, there are certain video formats which are supported under android. Using a different format appears to still work on certain devices, but can fail on others. For mp4 videos encoded with the H.264 AVC codec, the Baseline Protocol (BP) has to be used. FFmpeg can be utilized to convert videos into mp4 files which satisfy these requirements. The options
-vcodec libx264 -profile:v baseline -level:v 3.0
have shown to yield good results.