Comment 2 for bug 1014455

It sounds like gstreamer might have blacklisted some core plugins for some reason (maybe you've installed a conflicting version of gstreamer from source?).

Try removing the plugin registry files in ~/.gstreamer-0.10/registry* and start Clementine again.
If that doesn't work, remove the files again, run gst-inspect and look for error messages about failing to load libraries.