What does the subsequent apt-get calls say? sudo apt-get install gnome-desktop-environment sudo apt-get install gnome-themes-extras -- gnome package uninstallable on edgy https://launchpad.net/bugs/57334