no controlo nada de gnome, pero has probado a añadir el icono a mano? boton de la derecha propiedades y pinchas en el icono para asignarlo

Botón derecho->propiedades sobre el lanzador no viene nada parecido a cambiar el icono (en windows sí venía, podías ponerle el icono que quisieras).
Aquí una captura, estando en Gnome, de la carpeta "Escritorio" abierta tanto con Nautilus como con KDE:

no se muy bien que puede ser, has tenido en cuenta que en kde el escritorio es plasma y no hay iconos si no plasmoides? es más los lanzadores como tal no funcionan. Por eso la carpeta Escritorio es inutil en kde4.
has probado a generar esos lanzadores desde gnome arrastrandolos desde el menu de aplicaciones?.

Sí, he probado arrastrándolos. De hecho, en el menú "Aplicaciones", el icono sí sale bien, y si lo arrastro a un panel, también sale bien (en Gnome)

¿Por qué la carpeta escritorio es inútil en KDE? Si escoges vista de carpeta, sale el "Escritorio" (carpeta escritorio)

¿Los dos iconos más grandes son los plasmoides? ¿Y se puede desactivar (en KDE) que al darle con el botón derecho a algo del menú, se ejecute? Para poderlo arrastrar, digo.

El escritorio sí vale en Kde, ojo. Yo tenía instalado Gnome y el escritorio me apareció exactamente igual, pero en el plasmoide de Carpeta de escritorio, no en el fondo de la pantalla absoluto.
En gnome puedes asignar el icono a tu gusto. No tienes más que utilizar el botón derecho y propiedades como se ha dicho. Luego pinchas el la imagen del icono que te salga en la ventana emergente y buscar la ruta del que desees poner. Hoy mismo lo he hecho yo así.

Ah vale, que era pinchando en la imagen (y yo buscando algo que fuera "cambiar icono"...), no me había enterado cuando lo dijo shaola. Lo siento.

De todas formas, el que yo quiero asignarle es el propio icono que trae por defecto el lanzador (el que sí me sale automáticamente y correcto si le doy a "añadir este lanzador al panel" pero no si le doy a "añadir este lanzador al escritorio") y ponerse a buscar el icono manualmente es algo engorroso...
Por ejemplo, he tenido que hacer una búsqueda de todos los archivos llamados "scummvm" hasta que he dado con un archivo de texto que ponía:

?package(scummvm):needs="x11" section="Games/Adventure" \
title="ScummVM" command="/usr/games/scummvm" \
icon="/usr/share/icons/scummvm.xpm"

¿Será esto algo raro o mal configurado que tiene el nautilus (que creo que gestiona el escritorio en gnome)? Porque lo de que el icono salga correctamente en TODOS sitios menos en el escritorio, es un poco rarito...

Pues a mi me da la impresión que lo tuyo va a ser cosa de tener los 2 entornos instalados a la vez...

No creo, yo siempre tuve los dos y no tuve ese problema.

La ruta para buscar el icono por defecto es /usr/share/icons

Y ahí hay una carpeta que sera Kde, o kde4 o kdedefault, no recuerdo bien, ahora estoy en un puto Windows, pero es fácil de localizar.
En casa miro la ruta exacta.

Si la cosa no es buscar la ruta de los iconos (ya puse manualmente los que faltaban, y cada uno estaba en una ruta distinta, ninguna era /usr/share/icons).
La cosa era saber por qué pasaba...
Hace un par de días, instalé actualizaciones (las que avisa el gestor), y curiosamente el icono del Konversation se cambió solo (en una de las imágenes que adjunté se ve que tenía un icono diferente).