Unable to get Video + VideoJS to play MP4s on ANY Android device
Many issues with playback are usually due to improperly formatted/encoded files. Different browsers/devices do not support the same media formats in their implementations of HTML 5 video. This due to mainly patent issues, open-source vs. proprietary and disagreement over which is the "best" format.

To make your video work in the latest versions of all major browsers, you will need to serve your video in both WebM format and MP4 format. To guarantee the broadest range of browser/device compatibility you may also need to include the Ogg format.

WebM: Firefox 4+, Chrome and Opera 10.6+
MP4: Internet Explorer and Safari
Ogg: Firefox 3.5+, Opera 10.5+

Go to http://html5test.com/ using your test devices to see what formats are supported.

Helpful info:

http://www.longtailvideo.com/html5/#media_formats

http://www.longtailvideo.com/html5/formats/