AFAIR, a similar error can be generated by the shell if a perl script containing Windoze line endings and having execute permissions is run on a *NIX (specifically Solaris) box - the shell mis-understands the shebang line.
Update:
Thanx to almut for the nudge - when I say shell, I should've said OS (on/in which the shell runs).
A user level that continues to overstate my experience :-))
Those errors are typically along the lines of "Command not found", because the kernel does interpret the shebang line, but then doesn't find a perl binary ".../perl\r" (it's not the shell that interprets the shebang line — otherwise, how could you call a script via the exec* family of system calls, where no shell is involved?). In the case of the OP, the shebang line doesn't seem to be recognized at all, so the system defaults to using the shell to interpret the script.