Isso passou a acontecer comigo também. Uso o Ubuntu 7.04, somente GNOME. Tenho sim, algumas bibliotecas do KDE no meu sistema por ter instalado o K3B, mas creio que o problema não se deva a isso.
Desconfio que isso tenha surgido depois que tentei instalar o anjuta+glade (vi que várias bibliotecas do gnome2 foram instaladas)e logo que desisti desinstalei cada pacote instalado manualmente mesmo!
Desinstalei todo o openoffice para ver se resolvia o problema, e acabei instalando o Broffice.org (que na verdade tem apenas alguns pacotes a mais), e na primeira inicialização os ícones voltaram, mas fui usá-lo hoje, e lá se foram novamente!
Alguém sabe a solução?