I had the same problem recently after switching to Xubuntu 13.04. I could embed video but the frame appeared with "sound icon" (instead of question mark which appears on embedded videos) and gray frame appeared in presentation mode. Installing Oracle JRE did not help.
I am not sure what exactly helped in my case though I am quite sure the problem was GStreamer-related, probably due to some old configuration in my home directory.
~/.gstreamer-0.10 directory (if it is present).
Or try installing
gconf-defaults-service – I doubt this actually helped problem, but there may be some obsolete settings which get fixed this way.