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?