Works for me:

#!/usr/bin/perl

use CGI qw( :standard );

$cookie = cookie( -name    => 'sessionID',
                  -value   => 'xyzzy',
                  -expires => '+1h',
                  -path    => '/',
                  -domain  => '.foo.com',
                );
print redirect( -url    => 'http://login.foo.com', 
                -cookie => $cookie
              );
[download]

Do you have some other portion of the code outputting header stuff that would interfere? Why do you say it's not working. What client? IE? Firefox?