I couldn’t reproduce the issue with Administrator role. Can you try restoring the role, make sure the “Remove Non-Standard Capabilities” setting is disabled.
You are right about the setting to disable Nav menu permissions. Since this could affect the existing functionality of the site, I think this should be disabled by default and enabled by an option. I’ll soon have a release (possibly today).