I think the Shebang thing, although valid, is a red herring.

Other things may happen:

Bad interpreter, i.e. the program after #! could not be found. The Mac error message is at least similar.

/tmp>cat shebang.pl
#!/no/such/perl -w

use strict;
use warnings;

print 'Hello\n';
/tmp>chmod +x shebang.pl

/tmp>./shebang.pl
-bash: ./shebang.pl: /no/such/perl: bad interpreter: No such file or d
+irectory

/tmp>
[download]

Interpreter not executable:

/tmp>cat shebang.pl
#!/etc/passwd

use strict;
use warnings;

print 'Hello\n';pstree -al

/tmp>chmod +x shebang.pl

/tmp>./shebang.pl
-bash: ./shebang.pl: /etc/passwd: bad interpreter: Permission denied

/tmp>
[download]

Shebang not identified as such:

/tmp>cat shebang.pl

#!/usr/bin/perl -w
# ^- note: Shebang on second line, first line is empty!

use strict;
use warnings;

print 'Hello\n';
/tmp>chmod +x shebang.pl

/tmp>./shebang.pl
./shebang.pl: line 5: use: command not found
./shebang.pl: line 6: use: command not found
./shebang.pl: line 8: print: command not found

/tmp>
[download]

This also happens when there is an (invisible) Byte Order Mark (BOM) at the start of the file. What happens here?

The shell attempts to start ./shebang.pl via fork() and exec(), as usual. This will fail, because the kernel can't identify the file as binary executable or script with some interpreter (first two bytes aren't #!). At this point, a legacy mechanism in the shell kicks in. In the very early days of Unix, shell scripts did not have to have the shebang. If you chmod +x any text file and try to run it, but exec() fails, the shell will attempt to read it as a shell script. A little experiment shows this:

/tmp>echo 'pstree -Aal' >> shebang.pl

/tmp>./shebang.pl
./shebang.pl: line 5: use: command not found
./shebang.pl: line 6: use: command not found
./shebang.pl: line 8: print: command not found
init
  .
  .
  .
  |-sshd
  |   `-sshd
  |       `-sshd
  |           `-bash
  |               `-bash
  |                   `-pstree -Aal
  .
  .
  .
[download]

Update:

A little trick to ensure you don't run into the BOM trap:

/tmp>perl -e '$_=<STDIN>;print ord $_' < shebang.pl
10
/tmp>
[download]

This test must return 35 or the script does not start with the shebang. 10 is a LF, the end of the first line. 13 is CR, the end of the first line with MS-DOS or classic Mac line-endings, 32 is a space, 9 is a tab. Byte Order Marks may show up as 239 (UTF-8), 254 (UTF-16 BE), 255 (UTF-16 LE or UTF-32 LE), 0 (UTF-32 BE), 43 (UTF-7), 247 (UTF-1).

Update:

See also Re^2: Shebang behavior with perl

Alexander