I’ve tried the following just now:
1) Disabled the Object/Transient Cache (live site)
2) Disabled the 2 active plugins – lizatoms and SEO Ultimate
Both of these had no effect on the menu issue, unfortunately.
Would you be willing to look around on the site to see if I missed something? I’ve duplicated the site to the staging area for you.