Next things to try might be domain and path; it looks like you're not setting them. Still just guesses and it seems increasingly unlikely that it's the actual cookie that's the problem.

Best thing would be to try to get a *detailed* report of the exact steps that trigger it from an affected user. Including whatever Wireshark (or Live HTTP Headers or Fiddler or something) log for the entire process.

I've previously done extensive logs, thats what brought me to the conclusion that the browser itself is not setting the cookies. In fact, if I pass the session ID via cgi params, they can successfully login and use the system, but I really would rather the user not see that Session key in the url. This user in particular is ...err, should I say, computer illiterate? Getting them to pass wireshark logs would be near impossible (but may be necessary in this case). I'm going to add "path" and "domain" cookie vars as you suggested and see if that helps first. Then see if I cant walk this user through a wireshark installation and log...wish me luck, lol. Thanks for all the great suggestions, I'll report back when I know something.