O comando dpkg -S /usr/share/icons/ deve mostrar o pacote que você precisa reinstalar para restaurar seus ícones:
➜ ~ dpkg -S /usr/share/icons/
gnome-icon-theme-extras, gimp-data, gnome-colors-common, gnome-brave-icon-theme, alacarte, gnome-online-accounts, smplayer, eog, libreoffice-common, gcr, baobab, gnome-system-log, evince-common, emacs24-common, hicolor-icon-theme, libpeas-common, byobu, desktop-base, icedtea-netx-common, gnome-icon-theme, empathy-common, gnome-session-common, gnome-control-center-data, gnome-settings-daemon, gnome-power-manager, gnome-media, shotwell-common, cabextract, gnome-panel-data, libgweather-common, gnome-disk-utility, imagemagick, gdm3, openjdk-7-jre:i386, gnome-themes-standard-data, gnome-user-share, gparted, rygel, vinagre, cheese-common, gnome-bluetooth, iceweasel, file-roller, xchat, rhythmbox-data, seahorse, deluge-gtk, gnome-packagekit-data, gnome-icon-theme-symbolic, brasero-common, gnome-tweak-tool, aisleriot, gnome-accessibility-themes, ettercap-graphical, pidgin-data, zim, chromium, gconf-editor, dconf-editor, ibus, steam, gbrainy, network-manager-gnome, flashplugin-nonfree, synaptic, geary, tracker-gui, xterm, freeciv-data, gnome-applets-data, gsmartcontrol, wireshark-common, wireshark, upnp-router-control, ppstream, ibus-anthy: /usr/share/icons
Não é uma tarefa fácil, mas deve deixar você no bom caminho. Você pode reinstalar usando:
sudo apt-get install --reinstall package