それほど詳しくないのですが、いくつかやってみるべきことがあると思います。
(それとは別に使用しているUbuntuバージョンを教えてください。)
１.新しいユーザを作ってみて、新しいユーザでも同じ状況になるかどうか。
    これでシステム全体の問題か、個別のユーザの問題かが切り分けられると思います。
２.上記で新しいユーザでも同様の現象が起こる場合
    推測でしかないのですが、/etc/xdg/menus/applications.menu が壊れているのかもしれません。
    端末で sudo apt-get install --reinstall gnome-menus と入力してgnome-menusパッケージを入れ直したら
    なおるかもしれません。