I also upgraded from 2007. I figured out the problem.
The file I was working in was originally created using 2007. So all I had to do was create a new presentation in 2010 and copy/paste the old slides into the new file. Videos now work when inserted into this new 2010 file.