Tente:
sudo apt-get update && sudo apt-get autoremove && sudo apt-get autoclean
Se isso não funcionar, tente:
sudo apt-get update && sudo apt-get autoremove && sudo apt-get clean
Ao desinstalar o Remove vs Purge.
sudo apt-get remove <package-name>
os arquivos de configuração não são removidos.
sudo apt-get purge <package-name>
Pode ser mais adequado para o que você está procurando fazer. Como isso também irá limpar os arquivos de configuração.
EDIT: Isso não remove pastas ocultas. Aqueles precisarão ser removidos manualmente como sugerido por @Takkat e @Oli aqui:
( Como posso detectar e excluir todos os perdidos pastas de configuração? )