It would be good to automagically install the necessary gstreamer plugins when
we can't decode a file, using GStreamer's missing plugins support much like totem & rhythmbox does.
For reference, here's how totem does it:
*** Bug 14230 has been marked as a duplicate of this bug. ***
This should be fixed in all packages now.
At least Youtube properly informs me about missing plugins now.