Your problem might be that there is a CR after the #!/usr/bin/perl line, so the kernel will try to use the binary named "/usr/bin/perl\r" which of course does not exist.

There's been some post about this, I'll try to search it.

Update: ah, here is it: Re: Perl Script only runs with -w switch