Esta dica vai para os usuários do Debian e novatos como os que eu ensino Linux para não quebrarem muito a cabeça fazendo download disso e daquilo. Vamos lá:

Primeiro rode o comando:

$ sudo apt-get update (para ele atualizar a lista)

Depois é só rodar:

$ sudo apt-get install amarok

Depois de tudo instalado, execute o amarok e tente executar um arquivo em mp3. Ele vai pedir para instalar o suporte a mp3, clique em sim, sim; daí faça o que ele pedir. Se ele não mostrar o diálogo para instalar o suporte, atualize o amarok pelo gerenciador de atualizações ou pelo gerenciado de pacote Synaptic (bem provável por este último). Uso o Ubuntu 6.06 Dapper e fiz aqui e foi tranquilo. Qualquer coisa postem aqui.

Aqui vai para os que usam outro player como o kaffeine: instale a libxine e o gstreamer:

$ sudo gedit /etc/apt/sources.list

Desmarque todas as opções relativas a universe, multiverse e restricted. Execute:

$ sudo apt-get update
$ sudo apt-get install gstreamer0.8-mad

Não esqueçam de instalar a libxine:

$ sudo apt-get install libakode2-mpeg libxine-extracodecs

Espero ter ajudado!!!