I guess you need to unescape the URI in $new_location, i.e.

use URI::Escape;

my $location = "http://www.google.com/sorry/?continue=http://www.googl
+e.com/search%3Fq%3Dperlmonks";

my $new_location = $location;
$new_location =~ s/.*\/sorry\/\?continue=(.*)/$1/;
$new_location = uri_unescape($new_location);

print "   $location\n=> $new_location\n";

__END__
   http://www.google.com/sorry/?continue=http://www.google.com/search%
+3Fq%3Dperlmonks
=> http://www.google.com/search?q=perlmonks
[download]

That said, I don't get any captchas or sorries from Google (is this still your squid's sorry thing?), so I couldn't test it as is... but when I submit an incorrect search, e.g.

    http://www.google.com/search?=perlmonks
[download]

(i.e. missing q, as in your OP), Google redirects me to http://www.google.com/webhp, so I used that response to test, and when I rewrite the Location to

    if ($location =~ m|/webhp$|) {
        my $new_location = "http://www.google.com/search?q=perlmonks";
        $headers->header( Location => $new_location );
    }
[download]

things work fine for me, while with the escaped http://www.google.com/search%3Fq%3Dperlmonks I do get a 404 Google custom error page.