From the fm:
NOTE: If you're running into the "You do not have sufficient permissions to access this page." message in a wp_die() screen, then you've hooked too early. The hook you should use is admin_menu.
I am able to create menu items and submenus from hooks much earlier than admin_menu eg: plugins_loaded. In fact, it seems to work without any hook, at all, straight outta functions.php. WP 4.0.1. So, what gives? Is this old info?