I have had recurring problems with Joomla sessions and staying logged in with the Joomla's Remember Me plugin in the past.
Seems to be different issues depending on browser, etc, as you've mentioned before.
Now with latest Joomla version, when I log in - with the CB Login module - even with a successful login, I get the JERROR box and "Please login first" from languange string JGLOBAL_YOU_MUST_LOGIN_FIRST
Seems to happen only when I log out and back in without restarting the browser, so perhaps an interfering session cookie. As I logout, I get the same error message from "/component/comprofiler/login", and once that's set, it reappears on login. If I clear all site cookies before logging in again, I do not get the error message.
I was testing this in Chrome, and this latest version of Joomla Remember Me just doesn't work. I see it setting and storing Remember_Me cookies, but it fails to log me in automatically any more.