After upgrading to WP 3.4, private menu items that were previously hidden from non-logged in users are now visible. It is not a theme problem as I have activated Twenty Eleven, and the same problem emerges. I have de-activated all plugins to troubleshoot, and still no luck.
Interestingly, when I do a preview of any theme, the private menu items become invisible (and three extra menu items are added to replace them, like an extra home, and search and sitemap).
Here's a PDF showing four screen shots, to give you an idea of what's happening. http://tinyurl.com/hidden-menu-visible
The thing is, before upgrading to 3.4, it was working, the private menu items were hidden to users not logged in.
I am using Responsive theme (big thank you to Emil for helping me troubleshoot this far).