Can you tell me the format of the video you are inserting? If you are using .mp4 or .mov forrmat then you should have quick time player installed on your system.
Are you inserting the video through the Presenter Insert Video function or through the PPT Insert Media function?
Presenter will convert all supported video formats into FLV, except MP4, which it leaves as MP4. If you can have your video in either FLV or MP4 before inserting into Presenter, then it leaves Presenter's video conversion tool out of the list of possible problems, and you retain more control over video quality settings.