Tive o mesmo problema
etapas para resolver o problema ;
1- terminal aberto
2- digite os 2 comandos seguintes;
sudo apt-get install ubuntu-restricted-extras
Seguido por
sudo apt-get install ffmpeg gxine libdvdread4 icedax tagtool libdvd-pkg easytag id3tool lame libxine2-ffmpeg nautilus-script-audio-convert libmad0 mpg321 libavcodec-extra gstreamer1.0-libav
lembrando de digitar - y - para cada comando.
Isso deve resolver seu problema com o Rythembox e permitir que você reproduza arquivos de mp3, etc.