If you developed this script on Windows, it's possible that the script file has non-UNIX line endings. (The perl interpreter can handle them, but the shebang line is interpreted by the shell, and is not tolerant of incorrect line endings.) If this is the problem, the script may terminate with an error right at the shebang line.
When you bring a script over to UNIX from other OSes, check the file format, and correct line endings if necessary.
For example, using vi, when you open the script the file format is displayed at the bottom of the window. To force the file to UNIX format, enter the vi command