Ok, this is my last shot - I'm no expert by any means.
In your control panel, under Primary Settings > Advanced Options, do you have Cookie Path, Prefix, and Expiration Time set? If not, then your site is probably not generating a cookie at all. That's the only other thing I can think of.