I haven’t tried the Maintenance Mode plugin, but I had a similar situation come up with an in-house plugin today and one of my fellow developers clued me in.
That “insufficient permissions” page comes up when WP doesn’t think the page you’re trying to access has been registered under the admin menu. Poke around the plugin code and find the main activation document for it; it will probably have a bunch of add_menu_page() and add_submenu_page() calls on it. Check the URL for the page you’re trying to get to and make sure that it’s being added as a menu or submenu page somewhere. (Alternately, check to make sure it’s not getting misspelled, either in the link you followed or in the activation call.)
Obviously hacking the code for a plugin you’re trying to use is less than ideal, and I don’t know enough about your situation to be very specific, but I hope this helps.
