Pode ser necessário atualizar manualmente o cache de ícones, com algo parecido com o seguinte:
gtk-update-icon-cache -q -t -f /usr/share/icons/gnome
(substituindo gnome
pelo diretório contendo ícones que não são exibidos)
Dito isso, os scripts de pós-instalação do gerenciador de pacotes devem fazer isso por você.