Você realmente não precisa remover o gnome-screensaver, desabilitar o gnome-screensaver (e ativar o xscreensaver) em gnome-session-properties
Se você realmente deseja removê-lo, pode ser que gnome e gnome-core sejam pacotes meta, semelhantes ao ubuntu-desktop. meta packages são uma lista de pacotes a serem instalados.
Veja Metapackages do Ubuntu Wiki para detalhes