Parece que aptitude
contém novo código para resolver dependências. Este código é ... poderia ser melhor . : -)
No meu caso, a execução de apt-get upgrade
acabou de se oferecer para atualizar os 13 pacotes xorg e deixar o resto do meu sistema sozinho.
Então, se o seu aptitude
se enforca no gráfico de dependência (= ao instalar / atualizar, ele quer remover centenas de pacotes primeiro), experimente outra vez as ferramentas antigas.