Krileon, I'm having this same issue, and have tried all of the steps you suggested in this post (I think!), but when I request a new username or password I'm still getting re-directed to a page that says "Please login first."
My Joomla menu items for both the CB Member Login and CB Profile appear to be published and public, as is the module position for both. I've also toggled all of the options under SEO Settings in Joomla Global Configuration to "no" and cleared my cache. I don't have any other SEO modules or plugins installed. And I've checked the itemid, which is the same in the address bar of the page with the "Please login first" message as it is for the menu pointing to my CB Member Login. I also went back over the steps in the CB 1.9.1 documentation to set up the CB Member Login and CB Profile, and appear to have done it correctly.
I did get to a point once where I was sent my "forgotten" username, but can't remember how I got there. I do know that I was entering various URLs in the address bar to try to come up with the right combination. When I tried to retrieve my password using my username and email address, however, I was once again re-directed back to the same "Please login first" message. I've been unable since to successfully replicate getting the forgotten username sent to me.
Any further help you can give me to get this issue resolved would be much appreciated. I'm getting ready to do a big push for our registered users to begin using what we call our online Member Connection more often, and I just know that there are going to be lots of folks who've forgotten their usernames and passwords.
I'm using Joomla 2.5.18 and CB 1.9.1.
Thanks!