Eu instalei um pacote por engano e imediatamente removi (limpo para ser exato), mas diferente do próprio pacote, nenhuma das dependências instaladas ao lado foi removida. Eu não sei se é necessário ou não, mas se não, eu gostaria de removê-los.
man apt-get fornece informações de que o parâmetro autoremove é usado para remover pacotes que foram baixados automaticamente para satisfazer dependências de alguns pacotes e não são mais necessários.
Então, você pode usar sudo apt-get autoremove para remover dependências que agora são inúteis.
Fonte adicional: Ubuntugeek
Se o autoremove do apt-get não ajudar, você pode executar isso (precisa de aptitude , demora muito , como uma hora! - não faz ideia se isso pode ser feito mais rápido):
for i in $(dpkg -l | grep "^ii" | awk '{print }'); do aptitude why "$i"; done | grep "Unable to find"
Isto irá listar todos pacotes que o aptitude não consegue encontrar por que estão instalados (mas talvez você os tenha instalado manualmente)