Até onde sei o aptitude tem um controle de dependências mais bem feito.
Quando se instala algo usando o apt-get você instala o que deseja mais as dependências. O mesmo acontece com o aptitude
Quando se desinstala um pacote via apt-get, ele é desinstalado mas as dependências não, enquanto que no aptitude tudo vai embora (mas para isto acho que deve ter sido instalado com o aptitude também).
Em linhas gerais é isto. Tenho consciência que o aptitude é melhor, até já conversei isso com o André (pinduvoz) uma vez, mas por força do hábito sempre falamos apt-get....
[]'s
Cristiano