Reproduced with at least Totem and Rhythmbox.
To reproduce: remove gstreamer plugins necessary to play some video and audio files.
Launch Totem, and try to open an offending video file. PackageKit launches and offers to find the codec. That all goes fine, the install process is completed.
Now you're back at Totem. Try and play the file, and it'll say it doesn't have the codec necessary to play it. At the console you'll see:
** Message: Plugin registry updated, trying again.
** Message: Missing plugin: gstreamer|0.10|totem|XVID MPEG-4 decoder|decoder-video/x-xvid (ignoring)
** Message: All missing plugins are blacklisted, doing nothing
Restart Totem, try and play the same file, and it'll work fine straight away.
Now do the same thing, only with Rhythmbox and an audio file, and observe much the same effect (I didn't check what Rhythmbox's console messages are).
Since this happens in both Rhythmbox and Totem I'm guessing it's a gstreamer bug, but I suppose they could just both happen to be broken the same way...
Note that a v. similar bug in Ubuntu 9.10 was noted as a negative point in a review, so it'd be nice if we could have a fix for this available as a zero-day update.
Forgot to note - Dave Airlie notes that he's seen the same issue.
Fedora Bugzappers volunteer triage team