Corrigido! Veja aqui: link
Execute este comando no Terminal:
xdg-mime default nemo.desktop inode/directory application/x-gnome-saved-search
O problema era que o Ubuntu estava usando o Nautilus como navegador de arquivos, ao invés do Nemo.
(em uma nota lateral, por que todos os navegadores de arquivos têm nomes de coisas no oceano?)