If not on win32, make sure your shebang line (#!/usr/bin/perl) doesn't have a \r\n combo instead of just a \n at the end; bash doesn't strip the \r and looks for an executable named perl with the carriage return special character appended... This one pops up every now and then if you edit your scripts on a WinDOS platform..
And off-course I cannot ommit my usual PLP advocacy... :)