If you are getting either "cannot execute" or "bad interpreter" error when you run a perl script without implicitly passing through the perl interpreter then make sure that the line end characters are correct (i.e. \r\n vs \n). I think this is only important on the first line (the "shebang" line, according to perlfaq) because the shell tries to find "/usr/bin/perl\r" (or whatever path you specify) instead of just "/usr/bin/perl".
This was the case on both Linux and AIX, not sure if Windows behaves the same way. One quick way to convert \r\n to \n would be to run the following command:
perl -pi -e ‘s/\r\n/\n/’ whatever.pl