I'm having the same symptoms on some Magento installations(not only 1.9). In my case, it happens only in Chrome. I'm fixing this by logging in Firefox/Safari/Opera, and changing 'Use HTTP only' to 'No' in 'Session Cookies Management' of the 'Web' settings.
