Let's confirm what's going on. Can you please provide the output of `apt-cache policy amarok` and `cat /etc/apt/sources.list` ? -- Saying no to MP3 support on fresh install says that Amarok is now ready to support MP3 https://launchpad.net/bugs/58617