When a video is not working please consider the following :
- Did the upload itself finished successfully? - if not try to upload again
- Have you uploaded one of these formats ?
- Were you using a software to create this video (as opposed to shoot it with video camera) like Apple's iMovie? - some software all add a non standard information to the video, in this case try to export the video without those parameter and choose a standard codec
If your video still doesn't work send us a link to your page or the ID of your gallery and we will try to see what is wrong.