I'm not sure if you are using an ISP or not, but it's possible that the administrators have a policy of checking all programs before allowing them to run. The how and why of this varies, but I've encountered ISPs who place a red herring cgi-bin within the user's root web directory. The directory does not have execute permissions. Once admin has approved the program, they replace the file with a sym link to a copy that has been moved to the real cgi-bin.

That said, you are using CGI.pm and printing the header(), right?