Comment 17 for bug 30146

Yeah, I don't believe that this bug has anything to do with restarting the system.

It's fairly reproducible by installing packages that affect the gnome menu. Take the game "atomix" for example. It puts a menu entry under "Games". So to reproduce, insure that your menu is working correctly beforehand. Then install atomix and atomix-data in Synaptic. Now the menu will behave buggily. Then look at all of the sub-menus until they display correctly again. Then you can reproduce this bug again by uninstalling atomix and atomix-data!

This might not be a bug so much with gnome-panel as it is one with how Ubuntu's packaging system messes with the menu.