Typically, scripts would be placed in cgi-bin, not cgi-bin/perl, but that shouldn't make a difference.
If the script is under cgi-bin and has execute permissions (you should change the permissions to 755, by the way), the most likely suspect is the server configuration. ScriptAlias isn't...