I'm a big fan of going to the source on matters like this :-).
A really nice way of debugging cookie-related problems is by looking at your browser's "Page information" or "Site information" dialog box (in Opera, it's called "Edit Site Preferences", and is in the menu you get if you right click on a page). This dialog box will show you a list of all the cookies your browser has, including when they expire, the path and domain they apply to, and all kinds of other information. You could check to see if there is any reason that cookie might not apply or be sent to the HTML page from there.
Also: How do you get the session id to the browser? Do you use $session->header() or CGI::header or CGI::Cookie in your code anywhere? If you do, the actual cookie settings you use there might also be helpful in debugging your problem.