Houve erros de formatação nos arquivos. Com base em comentadores, só posso supor que algumas versões do gnome sejam mais tolerantes. De qualquer forma eu encontrei uma maneira bacana de fazê-los funcionar: Abra o diretório no dolphin e edite-o até que ele possa ser iniciado a partir do dolphin - somente quando isso funcionar, adicione o campo categories e eles aparecerão nos menus. No KDE você pode ter que executar: kbuildsycoca4 --noincremental primeiro se você não relogar.
As versões finais dos arquivos são:
cat ezdm.desktop
[Desktop Entry]
Categories=Game;RolePlaying;
Comment[en_US]=A tookit for ADnD Dungeon Master
Comment=A tookit for ADnD Dungeon Master
Exec=/usr/games/ezdm
GenericName[en_US]=Easy Dungeon Master
GenericName=Easy Dungeon Master
Icon=/usr/share/icons/hicolor/128x128/ezdm.png
MimeType=
Name[en_US]=EZDM
Name=EZDM
Path=
StartupNotify=true
Terminal=false
TerminalOptions=
TryExec=/usr/games/ezdm
Type=Application
X-DBUS-ServiceName=
X-DBUS-StartupType=
X-KDE-SubstituteUID=false
X-KDE-Username=
silentcoder@ravenriley ~/SOURCE/ezdm0/ezdm $ cat ezdm-console.desktop
[Desktop Entry]
Categories=Game;RolePlaying;
Comment[en_US]=EZDM Console Version
Comment=EZDM Console Version
Exec=/usr/games/ezdm --console
GenericName[en_US]=EZDM Console Version
GenericName=EZDM Console Version
Icon=/usr/share/icons/hicolor/128x128/ezdm-console.png
MimeType=
Name[en_US]=EZDM-Console
Name=EZDM-Console
Path=
StartupNotify=true
Terminal=true
TerminalOptions=
Type=Application
X-DBUS-ServiceName=
X-DBUS-StartupType=none
X-KDE-SubstituteUID=false
X-KDE-Username=
Caso isso ajude alguém mais. Acabei de lançar uma nova solicitação de compilação do PPA, portanto, os pacotes atualizados do ubuntu estarão disponíveis em breve.