If there is a ^M at the end of the first line, your shell is trying to run a program called /usr/bin/perl^M which doesn't exist. This problem seems to go away if you use -w (or some other argument) on the shebang line, as the shell can then find the /usr/bin/perl in #!/usr/bin/perl -w^M.