I just lost my mp3 playback in amarok (meaning that they were playing fine yesterday). So I did a bit of searching and found that the required packages for mp3 support are:
libxine1
libxine-extracodecs
libmand0
ubuntu-restricted-extras
I checked, and had all installed so I completely removed them along with amarok, and then installed them again, still no luck. Amarok still complains that there is no mp3 support and when I click the 'install mp3 support' button nothing happens. All my other media players (juk, noatun, xmms) have lost their mp3 support too.
I'm running kubuntu fiesty. Is there a magical package that eludes me? Or am I missing something obvious?
Any help is muchly appreciated
thanks

No ideas yet? 
I have some more information.
Noatun and XMMS both behave themselves, they can play mp3's
I've installed Exaile! (which does not use xine) and that works fine.

If I start Amarok as root, it will play mp3's, but if I start it as user, it gets upset.
I've started this thread on Ubuntu formus too: http://ubuntuforums.org/showthread.php?t=428576