PHP 301 Redirect, Impossible?

I have been trying to do a proper 301 redirect and have failed to do so. No matter what i try, its always a 302 redirect.

Returns a 302:

http_redirect("urlgoeshere", '', false, HTTP_REDIRECT_PERM)

Returns a 302:

header("HTTP/1.1 301 Moved Permanently");
header("Location: urlgoeshere");

Can anyone explain why these are coming back as 302's and not 301's? Server OS is linux, running PHP/5.2.14. Try it yourself.

I will give you guys a URL to try. I am testing using YSlow and Googlebot.

Should be 301: http://www.fantasysp.com/player/mlb/Albert_Pujols/1486349