I think it depends on which engine you use in the Amarok configuration. I use gstreamer so I installed gstreamer-plugins-extra-audio. But I'm running Fedora so your package name may be different.

By the way, Amarok is an incredible application. I love it.