Eu acho que você deve instalar o correspondente metapacote gnome (deve ser o mesmo que gnome-desktop-environment ) em vez de outros pacotes únicos. Provavelmente você está perdendo uma dependência.
Eu recomendo o seguinte comando:
sudo apt-get install gnome
Como alternativa, se você não quiser o ambiente completo com todos os programas adicionais que talvez não precise, também poderá instalar o desktop principal:
sudo apt-get install gnome-core