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.