yo solo se que amarok depende de phonon y phonon por defecto, en teoria usa gstreamer, a no ser que tu hayas instalado phonon con xine. entonces para que funcionen todos los formatos de audio, deberas instalar los plugins de gstreamer (gstreamer-ffmpeg para mp3, creo recordar, por darte un ejemplo)...
no se me ocurre otra cosa.