OK, para mim o que funcionou foi:
Pegue o arquivo applications-kmenuedit.menu gerado na primeira vez que você faz um save dentro do KMenuEdit, limpe a entrada "bogus" (ou qualquer mudança necessária para fazer com que o KMenuEdit realmente salve um arquivo lá), e copie isso para /etc/xdg/menus
ou ~/.config/menus
. Arquivo Mágico: bah!