Yup, this is what the problem is. The #! line is most likely "/usr/bin/perl\r\n", and the carriage return is putting the cursor back to the beginning of the line (which makes the shell's error message apparently start over with no path). Whenever you get strage error messages like this using od or your platform's variant of strace can be enlightening in seeing exactly what's being output or exec'd.