If you used CGI's named arguments-style, there's no need to craft your own 'Set-Cookie' header: redirect will do it for you, just like header.

print $cgi->redirect( -uri => $new_url, -cookie => $cookie );

    --k.