Para determinados serviços, você precisa do decodificador de mp3 que não está instalado no Ubuntu, por padrão.
Dependendo da versão do gstreamer instalada (você pode verificar pelo dpkg -l gstreamer *) você precisa instalar
sudo apt-get install gstreamer0.10-fluendo-mp3
ou em sistemas mais novos
sudo apt-get install gstreamer1.0-fluendo-mp3
Você pode encontrar a descrição completa no link do Nuvola FAQ # 2011