I've been running wordpress for a couple of years and never had this issue.
I was working on a new website when I did a couple of changes. Nothing serious, just uploading a plugin and changing the content of a couple of pages. Suddenly, I noticed that the menu bar navigation for visitors had disappeared. I don't know exactly when but it's not there... These are the things that I did after this happened.
-Upgrade to new version of WordPress. (I was running 3.4 and I upgraded to 3.4.1.)
-Deactivate my plugins and put them in active mode after confirming the menu wasn't there after, during or before deactivation.
-Delete my old menu and create a new one. (It wasn't the solution either). After that, I deleted all my plugins but, again, It wasn't the solution.
- I checked my console using Google chrome trying to find syntax errors but I didn't find anyone.
- Finally I look if there was another person with the same problem in this forum but I haven't found anyone with this problem.
I don't know what else I can do. I will appreciate a lot your suggestions. I feel a bit obfuscated... :-( Here you can see what I'm talking about: http://goo.gl/P1H4X