I'm guessing that homebrew doesn't actually replace the system perl, which is the one you are trying to run (#!/usr/bin/perl). Maybe try changing that to #!/usr/bin/env perl or calling your script as perl script.pl. If that doesn't work, you'll probably need to fix your path or put the full path to homebrew's perl on the shebang line.