Instale o python-gi: sudo apt-get install python-gi
Caso isso não funcione (improvável), instale o python-gobject: sudo apt-get install python-gobject .
No meu sistema, python-gi foi o pacote que faltava. Eu não instalei python-gobject em tudo.