If you are running a script via the command line (and you have SSH access enabled), or you are uploading a perl script to place in the cgi-bin, the perl interpreter is located at /usr/bin/perl, not /usr/local/bin/perl.
Also, it is important that when you upload a script from a Windows (or Mac) system to be run on our servers (which use Linux), the upload must be completed in ASCII mode (not Binary mode) unless you know what you are doing.
The shebang line (i.e. the first line of the file that starts #! tells Unix/Linux which interpreter to use to run the script) is sensitive to the Carriage Return (or \r) character - the system expects it to end with a Linefeed character, or \n. Windows systems use \r\n to signal a new line, whereas \r alone is used with Macs). Therefore, if a \r (or any other) character is found before a \n in the shebang line, it will be considered part of the program location and the script will fail to run.
If this happens via the cgi-bin, you will probably see a Server Misconfiguration Error (500 Error), as no headers are returned. If it's via the command line, you will probably find a message saying that the program /usr/bin/perl cannot be found instead (actually, it's /usr/bin/perl\r cannot be found).