Eu instalei usando o PPA, mas não funcionou. No entanto, a instalação usando o PIP funcionou bem:
sudo apt-get install python-pip git-core
sudo pip install git+https://github.com/nvbn/rhythmbox-gmusic.git#egg=rhythmbox-gmusic
Eu também instalei python-dateutil, python-requests e python-validictory.