I am having similar problems both with login and also registration. We have been running with CB for some 4 years now, but for some reason I am now getting authorization issues, both on public registration page, but also sometimes on login attempts. Also requesting a lost password is also consistently failing.
I am running Joomla 2.5.16, CB 1.9.1, CBSubs 3 GPL. I have disabled registration on Joomla side. My Profile menu was actually under a registered menu (which I have not had a problem with for many months, so why suddenly now?). I have set the top menu AND the Profile menu item to Public, cleared cache, cleared temp dir, etc, but i have the same problems.
Any other ideas on how to resolve? Currently no users can register to this 2000+ user site