I've given my newly created user the permission to "Administer menus and menu items " however, when I log in as the new user I cannot administer the menus... Why might this be? The user doesn't have the permission to administer blocks, if that makes any difference?
Based on the comments, I think the issue is that your user needs the "Use the administration pages and help" permission, under the System category.
You may need to enable the followings in
Contextual links Use contextual links Use contextual links to perform actions related to elements on a page. Overlay Access the administrative overlay View administrative pages in the overlay. Toolbar Use the administration toolbar