Por padrão, apt-get autoremove é muito conservador, o que resulta no comportamento que você está vendo. Enquanto apt-get install considera apenas dependências diretas e recomendações por padrão, apt-get autoremove também considera sugestões (dependências muito fracas). Isso é assimétrico e significa que por padrão , apt-get autoremove não necessariamente desfaz completamente a instalação de um pacote.
Assim, no seu caso, instalar o checkinstall extraiu vários pacotes, e todos acabam sendo considerados não removíveis por apt-get autoremove ; por exemplo, build-essential é mantido porque apt (que é definitivamente necessário) sugere dpkg-dev , que recomenda build-essential . Você encontrará relacionamentos desse tipo para cada pacote enviado por checkinstall .
Para corrigir isso, você pode adicionar
Apt::AutoRemove::SuggestsImportant "false" ;
Com essa configuração, apt-get autoremove encontrará mais pacotes para remover. Como seu sistema foi instalado recentemente, ele deve ser seguro (com isso, quero dizer que a assimetria mencionada acima não causará muitas surpresas, porque você não instalou muitos pacotes); mas examine a lista de pacotes que serão removidos antes de realmente removê-los!