I am having this same problem w/ 1.3.4.
My server & Forum are set to the same timezone, and I've even tried the hacks mentioned to increase the expire time on the cookie.
I thought that had solved the problem, but only for certain accounts which is the really weird thing. I can login no problem now with my admin account, but several users cannot, they are getting the:
You appear to have logged in successfully, however a cookie has not been set. Please check your settings and if applicable, enable cookies for this website.
I have the verified trying to login for the user from my computer, and I get the same thing. So that throws out all the posts about this bug having to do with the users time clock, as why would I be able to login to my account, and not to his on the same computer?
Anatoly - My findings here go against the 3 possible scenario's you have mentioned. as everything is set correctly everywhere.