I've fought this problem before and it turned out that the RFC does not allow for redirection to occur with anything but the GET or HEAD method. What I've done instead is to use LWP and the HTTP::Request method to do the POST and then give the result back to the user's browser. For instance:

my $req = new HTTP::Request POST => 'http://www.somewhere.com';
$req->content_type('application/x-www-form-urlencoded');
$req->content($content);
print $res->content;
[download]

Hope this helps. I haven't found any cleaner solution.