I think I figured out the issue. I asked the site owner to only give me design permissions. I didn't want a full admin role. However, with only design control, I could edit pages, but I couldn't gain access to change the header navigation. Once I was given full permissions that wasn't an issue.
Good luck with anyone else having this problem, it's extremely frustrating!