Tente abrir o Ubuntu Software Center, localizando o Rhythmbox e instalando-o. Se o Centro de Software informar que já está instalado, você poderá abrir um terminal e digitar o seguinte:
gksudo apt-get -y install --reinstall rhythmbox
E, em seguida, insira sua senha de administrador (quase sempre necessária para instalar as coisas) e deixe-a rodar. Quando terminar de reinstalar o rhythmbox, verifique se está disponível novamente.