You've most likely got an issue with your line endings. What would be happening is that you've got a carriage return at the end of the first line, so *nix is looking for a binary at "/usr/bin/perl\r" instead of the correct "/usr/bin/perl". Try running this one-liner on the file by replacing 'foobar.qux' with the name of your file, and then try running the perl script again.

$ perl -pi -e 's/\r\n/\n/;' foobar.qux
[download]