Para poder decodificar e reproduzir arquivos MP3, você precisa instalar o decodificador necessário que não está instalado no Ubuntu por padrão, e são fornecidos no pacote chamado "ubuntu-restricted-extras".
Execute isso em um terminal para instalar o pacote:
sudo apt-get install ubuntu-restricted-extras
Após instalá-los, tente importar seus arquivos MP3 novamente.
Se falhou (Qual é o seu problema agora!) É provavelmente porque o banco de dados estava corrompido.
Assim como A.B. Você pode simplesmente excluir o banco de dados e reimportar:% rm ~/.local/share/rhythmbox/rhythmdb.xml
Nesta fase, não deve haver qualquer problema com o Rhythmbox importar arquivos mp3.