We encountered a really strange problem whereby the menus would disappear on only a specific page that had access denied on it. After lots of research and trying fixes, we found out it was an order of operations thing going on for hook_init. So, we used utility module to add weights to the modules listing and make simplemenu float to the top. That fixed it.

Hope this helps anybody who encounters a similar problem.