Jo crec que s'estan barrejant coses.
De totes les eines que es comenten la pregunta incial és apt-get vs aptitude ja que són dues eines complementàries: fan el mateix de maneres lleugerament diferents. apt (a seques) o dpkg o d'altres que s'han comentat són eines que treballen amb paquetes però no al mateix nivell.
Dit això la pregunta apt-get vs aptitude és bona i sempre vigent. Per desgràcia (i fortuna al mateix temps) és un tret de les distribucions de programari lliure: hi ha opcions.
Jo en general faig servir aptitude perquè resol millor les dependències. Tret del tema de les dependències i la resolució de conflictes crec que no hi ha diferència (ni n'he detectat cap). Inicialment recordo que la gran diferència era que aptitude instal·lava paquets per dependència i els marcava de manera especial de forma que si en un procés posterior veia que un paquet instal·lat per a satisfer una dependència quedava sol i ningú depenia d'ell aleshores el desinstal·lava. Ara em sembla que apt-get fa alguna cosa semblant.
El que ha comentat el company tictacbum jo ho he vist en diverses guies d'actualització de Debian. En alguna m'han aconsellat aptitude i en d'altres apt-get. Imagino que depen del moment de maduresa de l'eina i del que estigui més provat en cada versió.
El que he llegit fa poc és que aptitude ha quedat sense mantenidor, però imagino que és un problema temporal.