Comment 19 for bug 1103747

I had the same problem on my F18 (also had many problems when switching from F17 to F18).
Especially, I had the following:
** (totem:31451): WARNING **: Element 'cluttersink' is missing, verify your installation

(totem:31451): Gtk-WARNING **: A floating object was finalized. This means that someone
called g_object_unref() on an object that had only a floating
reference; the initial floating reference is not owned by anyone
and must be removed with g_object_ref_sink().

I also ran, as elad suggested (thanks to him :):
rm -f ~/.cache/gstreamer-1.0/registry.*

and now it works fine!