Hát, ha ennyire szétszeretnéd választani, akkor az összes .desktop fájlba írd be az OnlyShowIn=KDE -t vagy a NotShowIn=KDE -t. Az eldöntés elég egyszerű, mert a KDE-s alkalmazások a /usr/share/applications/kde4 könyvtárban vannak, a Gnome-osak pedig egyel feljebb. Ezt lehetne automatizálni is akár, de nem teljesen ugyanazt az eredményt adná, mint amit szeretnél, mert értelemszerűen Gnome alatt nem látszódnának a KDE-s cuccok (és vice versa). Amit konkrétan elszeretnél érni, azt már nagyobb munkával lehetne kivitelezni, írni kellene egy saját .menu fájlt (xml), valamint ugyancsak ki kellene egészíteni az összes .desktop fájlt. De a közelgő Unity miatt - amivel nem lenne kompatibilis -, ezt nem ajánlanám.
Jah, és persze a .desktop fájlok szerkesztése után szükséges a cache frissítése, különben újraindítás után visszaáll az eredeti felállásra minden.