Depois de muita pesquisa, decidi reinstalar policykit-1 package. Quando eu fiz sudo apt-get install --reinstall policykit-1 , recebi uma mensagem dizendo que o pacote não pôde ser instalado porque não estava disponível no repositório (desculpe pela falta da mensagem exata!).
Então, eu corri:
apt-cache policy $(dpkg -l | awk 'NR >= 6 {print }') | less
Isso me mostrou que vários pacotes tinham versões como 0.105-1ubuntu1pitti2 , enquanto a versão disponível dos repositórios do Ubuntu era algo como 0.105-1ubuntu1 . Parece que gnome3 ppa extraiu pacotes de este ppa .
Então, eu corri o seguinte comando (os nomes dos pacotes são aqueles que tinham as versões pitti instaladas):
sudo aptitude install dbus=1.6.8-1ubuntu6 dbus-x11=1.6.8-1ubuntu6 gir1.2-polkit-1.0=0.105-1ubuntu1 libdbus-1-3=1.6.8-1ubuntu6 libdbus-1-3:i386=1.6.8-1ubuntu6 libdbus-1-dev=1.6.8-1ubuntu6 libpolkit-agent-1-0=0.105-1ubuntu1 libpolkit-backend-1-0=0.105-1ubuntu1 libpolkit-gobject-1-0=0.105-1ubuntu1
O comando acima instalou as versões oficiais do repositório do Ubuntu dos pacotes. Os números de versão vêm da saída do comando apt-cache policy acima. E agora tudo está funcionando.