Dica testada no Ubuntu 16.04 com Gnome 3.20.

Uma forma prática de eliminar pacotes órfãos no Ubuntu, é usando o removedor de pacotes órfãos! :D

Pacotes órfãos são aqueles pacotes (dependências) que estão no sistema, mas que não estão sendo utilizados por nenhum outro software. Ou seja, são restolhos, sem função alguma no sistema, que acabaram ficando lá depois que você removeu algum programa.

Instale o removedor com:

sudo apt-get install gtkorphan

Depois busque por "remover pacotes órfãos" nos programas ou use o comando:

sudo gtkorphan É bom fazer uma limpeza de vez em quando!

Abraço.