Many suggest to delete ~/.gstreamer-0.10/ and install gstreamer0.10-plugins-bad.
But when I try installing gstreamer0.10-plugins-bad apt-get tells me it's installed at latest version. And when I delete ~/.gstreamer-0.10/ and try playing an m4a clementine still says that the plugin is missing and I find the .gstreamer-0.10 there! (apparently regenerated by clementine).
My clementine is Version 1.2.3 and not installed from the official ubuntu repos. (coz the network remote doesn't work with them. Nevermind.)
Best Answer
Use dev version of Clementine, solved my problem.
ppa:me-davidsansome/clementine-dev
https://launchpad.net/~me-davidsansome/+archive/ubuntu/clementine-dev