Recentemente ao usar alguns arquivos no formato MP3 em conjunto com o programa de gravação de cd/dvd mais popular do Linux, o K3B para criar um cd de áudio, tive uma infeliz surpresa, sempre ao arrastar o arquivo da mp3 para o local onde ficam os arquivos a serem gravados e/ou convertidos em tempo de execução, o K3B me emitia uma mensagem de erro em inglês (obviamente) dizendo que não tinha suporte a esse tipo de arquivo e algo sobre não ter o codec apropriado. Logo em seguida pensei em como resolver esse problema e a primeira coisa que eu fiz foi ver quais os pacotes e codecs tratavam disso, digitei:

$ apt-cache search mp3 k3b

Como resultado saíram os pacotes essenciais que você deve instalar, tais como LAME e LIBK3B2-MP3, portanto:

# apt-get install lame libk3b2-mp3

A partir daí reinicie o seu k3b e pronto, problema resolvido.