Ok, descobri qual era o problema: permissões erradas em /media/<username> .
Se você tiver a mesma mensagem de erro, então umount everything, vá para /media e exclua seu diretório. O Nautilus irá recriá-lo com (espero) as permissões certas.
AVISO: Certifique-se de que nada esteja montado int /media/<username> , porque você pode perder seus dados.
NOTA: Se este problema ocorrer novamente, criarei um relatório de erros no launchpad.