So very strange, this issue is.
I'm not having any issues at all with Chrome on Mac (version 41.0.2272.118). Not sure about the others, as I tend to only use Chrome. I can have a go with the other browsers and see whether I get different results, but everything seems to be working perfectly from here on the cookie front as far as I can see.
I've checked the cookie settings and there are no options to turn them on or off, or reset, or anything like that. Otherwise everything seems in order on the admin end.
I'm at a loss as to work out why this is happening...