I guess nobody else is replying because they don't know. It really does sound like the problem is with the individual browser settings, although I know you said there are several people with the problem.
I'm just a forum-owner like you, and I just know that I'm not having your problem, nor are any of my users. Did you reboot your browser after adding a cookie prefix?
