Sua saída de rastreamento de erro fornece uma pista sobre isso:
GLib-GIO-CRITICAL **: Settings schema 'org.gnome.rhythmbox' is not installed
O aplicativo está procurando por configurações do banco de dados gconf (dconf?) que não existem.
É provável que você precise instalar a versão do repositório do rhythmbox ou, possivelmente, forçar a reinstalação para garantir que os valores do esquema sejam criados.
ou seja,
sudo apt-get install rhythmbox
ou
sudo apt-get --reinstall install rhythmbox
Uma vez que o rhythmbox e seus esquemas associados estejam corretamente configurados - qualquer versão alternativa também deve ser capaz de rodar.