Former examples I have seen, only dealt with adding to an existing menu.

-
possible duplicate of How make AddMenuCommands work in an init.m –  Szabolcs May 30 '12 at 16:25
Or maybe this one: mathematica.stackexchange.com/q/907/12 –  Szabolcs May 30 '12 at 16:26
I was too quick to mark as duplicate, I am sorry. You are right that the other examples add to existing menus, and don't add a new menu. –  Szabolcs May 30 '12 at 21:00
AFAIK you can only do this by manually altering the MenuSetup.tr file -- but will be interested in other methods are available. –  Mike Honeychurch May 30 '12 at 23:31
@Szabolcs No problem :-) –  magma May 31 '12 at 0:48
You can't add an entirely new menu using AddMenuCommands. We have it from John Fultz here: