What application are you testing the movie in? What version of Acrobat or Reader?
I am using Acrobat reader X .
Do other PDFs containing videos work OK?
I have just tried another video and it seems to work ok, so there may have been a problem with the video file.
It won't play on Adobe reader 8 or 9 - Do videos only work on versions 10 and 11 ??
In Acrobat Reader, check the Multimedia Trust (legacy) setting. You can set the permissions of how the media players handle multimedia files. The settings are: Prompt, Always and Never. If "Never" is applied, then you would need to change to one of the other settings. Also, you have individual settings for Quicktime and Flash. And individual settings for trusted documents and other documents.
Keep in mind, these are application settings, and will only affect your app, not the document and how others will experience the multimedia files.