print $query->redirect('http://somewhere.else/in/movie/land');
redirects the browser elsewhere. If you use redirection like this, you should not print out a header as well. As of version 2.0, we produce both the unofficial Location: header and the official URI: header. This should satisfy most servers and browsers.
One hint I can offer is that relative links may not work correctly when when you generate a redirection to another document on your site. This is due to a well-intentioned optimization that some servers use. The solution to this is to use the full URL (including the http: part) of the document you are redirecting to.
You can use named parameters:
print $query->redirect(-uri=>'http://somewhere.else/in/movie/land', -nph=>1);
The -nph parameter, if set to a true value, will issue the correct headers to work with a NPH (no-parse-header) script. This is important to use with certain servers, such as Microsoft Internet Explorer, which expect all their scripts to be NPH.