You don't mention it: are you sure the browsers you're testing with are actually getting the cookies? Look at the actual headers returned by your application -- I've found wsnitch to be an invaluable application for this, although if you can do so just using telnet myhost 80 and typing in the request by hand is easier. (Using LWP for this is, of course, always an option :-)

Another thing: what happens when you do something like:

 my $header = $cgi->header( -type => 'text/html',
                            -cookie => $cookie );
 warn "Header sent to client:\n<<$header>>\n";
 print $header;
[download]

Just so you can be absolutely certain that the browser is getting the right header. I've been bitten by this more times than I can count :-)

Chris
M-x auto-bs-mode