OK, this is just a shot in the dark, but are you sure your perl binary is in /usr/bin ? I use both Solaris and Linux, and in Solaris the perl binary is located in /usr/local/bin. So every now and then, I type in the wrong path in the she-bang line.

As I said, a shot in the dark...