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.