Esse sábado peguei o KUbuntu 7.04 pra dar uma fuçada, já que abandonei o Windows e meu Slackware não estava em casa. Após ter instalado e feito alguns ajustes fui escutar música e vi que não havia suporte pra mp3, procurei na net e um tópico mais distorcido que outro, no fim eu consegui de outro jeito e é isso que eu vou explicar.

Após alguns tentativas frustradas tentando usar o apt-get, eu fiquei com raiva e comecei a procurar pelos pacotes citados, o pacote que realmente interessa é o libxine1-ffmpeg, só que para instalar ele você precisa do pacote libmad0, o que eu fiz foi simplesmente baixar os 2 e instalar manualmente.

Eles podem ser achados na página de pacotes do Debian. Ai vão os links:

libmad0:
http://ftp.br.debian.org/debian/.../libmad0_0.15.1b-1.1_i386.deb

ff-mpeg:
http://ftp.br.debian.org/debian/.../libxine1-ffmpeg_1.1.7-1_i386.deb

Após baixar é muito fácil, é só clicar com o botão direito no:

Libmad0 > KUbuntu Package Menu > Install Package

Depois é só fazer o mesmo com o ffmpeg e pronto! Seu Amarok já pode reproduzir seus MP3's ;D

Espero ajudar alguém, pois em alguns lugares está meio mal explicado como fazer isso...