Prova a fare un:
apt-get -f install
dovrebbe rimetterti a posti gli eventuali pacchetti difettosi.
Dopodichè puoi eliminare quello che vuoi tenendo però presente che alcuni programmi (come synaptic) necessitano di librerie gnome.
Quindi non potrai certamente eliminare completamente Gnome.

mcz