As dvergin points out, browsers are perfectly capable of handling cookies sent with redirects. Fortunately, CGI.pm also supports it, though you have to dig a bit to be sure. The CGI pod indeed does not mention such a procedure, but it is supported. Browsing the code of the redirect sub in CGI.pm you can see:

#### Method: redirect
# Return a Location: style header
#
####
'redirect' => <<'END_OF_FUNC',
sub redirect {
    my($self,@p) = self_or_default(@_);
    my($url,$target,$cookie,$nph,@other) = $self->rearrange([[LOCATION
+,URI,URL],TARGET,COOKIE,NPH],@p);
    $url = $url || $self->self_url;
    my(@o);
    foreach (@other) { tr/\"//d; push(@o,split("=",$_,2)); }
    unshift(@o,
         '-Status'=>'302 Moved',
         '-Location'=>$url,
         '-nph'=>$nph);
    unshift(@o,'-Target'=>$target) if $target;
    unshift(@o,'-Cookie'=>$cookie) if $cookie;
    unshift(@o,'-Type'=>'');
    return $self->header(@o);
}
[download]

Note in particular the -Cookie bit. And nicely enough, this actually works as intended. I've used bits like the following successfully:

$cookie = cookie(
  -name    => $COOKIE_NAME,
  -value   => $session_key,
  -expires => $COOKIE_EXPIRE,
  -path    => $SCRIPT_PATH,
  -domain  => $SCRIPT_DOMAIN,
  -secure  => 0
  );

...

print redirect( -uri => 'view.cgi', -cookie => $cookie );
[download]

I admit I'm not sure why OP's bit fails. r.jospeh, take a look at the cookie files for the site you're connecting to in order to make sure they're correct. Offhand, I'd suspect (like dvergin) a difference in $in{usr} and $usr is the problem. If not, you could set up a dirty HTTP server (with HTTP::Daemon, for instance) to see what's going on with your logout cookie.