gnome-icon-theme
está no repositório Universe, que você precisa ativar:
sudo apt-add-repository universe
e, em seguida, execute a atualização por:
sudo apt-get update
Agora você pode instalar o pacote por:
apt-get install gnome-icon-theme
Você também pode instalar gnome-icon-theme-full
se o acima não funcionar por qualquer motivo. Observe que esses pacotes têm suporte multiarch.