Essa é uma dica rápida pra quem está passando por esse problema. Aconteceu comigo e após uma pequena pesquisa, consegui resolver.

O procedimento foi testado no Linux Mint Debian Edition, mas deverá funcionar normalmente no Ubuntu e Debian.

Pelo que pesquisei, o problema não é no Amarok, mas sim no Phonon, que é uma API multimídia criada para abstrair o gerenciamento multimídia no KDE. Além de outras coisas, isso faz com que o Amarok possa funcionar no Windows e MacOS, por exemplo.

Enfim, sem entrar em maiores detalhes, o post que encontrei me sugeriu trocar o pacote phonon-backend-vlc pelo phonon-backend-gstreamer. Pra isso, digite o seguinte no Terminal:

sudo apt-get update
sudo apt-get remove phonon-backend-vlc
sudo apt-get install phonon-backend-gstreamer

Depois é só fechar e abrir o Amarok, que deve funcionar normalmente. Pelo menos funcionou comigo 🙂

Mais informações: