Para tocar mp3 é necessário apenas esse codec abaixo:
sudo apt-get install -y gstreamer0.10-plugins-ugly
Geralmente essa mensagem de erro seu acontece quando a pessoa baixa um vídeo ou música protegido contra pirataria, tipo baixado no limeware e outros p2p.
Ou às vezes a pessoa baixa um arquivo de mídia e não existe é apenas cavalo de tróia ou vírus.