I was having a similar problem. I had seen the menu's disappear before but Menudrake always fixed it. I installed fluxbox and the menu disappeared/emptied and menudrake wouldn't fix it.
I ran the "update-menus -v" as root and it gave the following error.
In file "/etc/menu/menudrakeentry", at (or in the definition that ends at) line 7:
[...] package="menu" section="Fluxbox/Styles/" title=""
[...] ^
Missing (or empty) tag: title
This tag needs to defined for the menuentry to make sense.
Note, BTW, that update-menus re-arranges the order of the
tags found in the menu entry files, so that the part above
isn't literal
/etc/menu-methods//gnome-mime-data-applications: Aborting
I went in and edited the menudrakeentry file and put flux into the title field and everything is back to normal now after updating the menu again.