No, I didn't have this problem before the uninstall. Yes it is the same for all users regardless of user type. I did use the "Merge User Databases" when I installed it. Yes, I can still log in to the Administrator by going to the url for it. Yes, the users are showing up the user list, including the new user that I signed up for testing purposes. I have tried clearing all cookies, but it didn't have any effect.
Before I uninstalled I could see the Menu items. After the uninstall, I still had the items visible until I clicked on a link which reloaded the page.
If I set the "Show UnAuthorized Links:" option to yes, the links show up, but they show up for non registered users as well. As it is now, registered users can only see public items, except that they can see the User Menu.