Consegui corrigir este problema, reinstalando o pacote gvfs-backends. Eu tive alguns problemas sérios fazendo isso, porque o apt-get estava me dizendo, que meus pacotes gvfs estão quebrados, não me deixe reinstalá-lo (veja aqui: Como consertar o pacote GVFS quebrado? ). Então eu purgou:
sudo apt-get remove --purge gvfs-backends
Baixou o pacote aqui link e o instalou executando o seguinte comando:
sudo dpkg -i gvfs-backends_1.10.0-0ubuntu1_amd64.deb
Após reiniciar minha máquina, eu consegui trabalhar novamente, apesar do gerente de pacotes ainda estar me dizendo que o pacote está quebrado.