Ho finalmente scoperto leggendo questo post sul forum di debian perchè (a volte) il comando

sudo aptitude install nomepacchetto

cerca di rimuovere tutti i pacchetti dell’ambiente gnome. Se invece di aptitude usate apt-get il comando

sudo apt-get install nomepacchetto

vi consiglia di rimuovere i pacchetti inutili tramite

sudo apt-get autoremove

Se date conferma ad aptitude o se usate l’autoremove di apt-get, vi troverete senza l’ambiente gnome e sarete costretti a reinstallare tutto.
Se fosse capitato anche a voi, la motivazione, come dice il post, è relativa al fatto che gnome è installato a partire da un metapacchetto.
I metapacchetti non sono esattamente pacchetti reali ma solo wrapper – ovvero contenitori o io direi alias – per il pacchetto reale; per la cronaca lo scopo dei metapacchetti è far corrispondere al metapackage il pacchetto reale con la versione di volta in volta più recente. Quindi i gestori di pacchetti (apt-get e aptitude) non si rendono conto delle dipendenze tra i vari pacchetti gnome considerandoli inutili.
Il problema si può risolvere o evitando di installare il metapacchetto e installando invece gnome nella versione più recente oppure semplicemente lanciando

sudo aptitude keep-all

…che serve a mantenere tutti i pacchetti installati finora. Lo svantaggio sta ovviamente nel fatto che l’opzione keep-all mantiene anche quei pacchetti non dipendenti da gnome che non sono più necessari e che potrebbero essere rimossi con l’autoremove. Quindi il keep-all è consigliabile solo dopo una installazione fresca dell’ambiente gnome tramite metapackage.
Spulciando in giro (ad esempio qui) ho anche capito meglio la differenza tra apt-get e aptitude e quando conviene usare l’uno anzichè l’altro e viceversa.