Na minha instalação Debian, gnome-core tem uma dependência necessária em iceweasel . Se você tentar desinstalar o iceweasel , por definição, você quebrará a instalação gnome-core , o que significa que também precisa ser desinstalado. E gnome tem uma dependência necessária em gnome-core ; enxaguar, repita. Então, você está meio preso.
Esse estado de coisas é possivelmente um bug de embalagem do GNOME, e gnome-core deve estar mais apropriadamente dependendo do pacote virtual gnome-www-browser ou www-browser .