Two things via http://support.hostgator.com/articles/specialized-help/cgi-troubleshooting
First what did you set to 755? the file, the directory? BOTH? it has to be BOTH at 755.
Setting the directory permissions to 755 should always be sufficient. If you do set any directories to rwxrwxrwx, then any Perl scripts located inside of this directory will not execute!
Second you show #!/usr/local/bin/perl
The first line of your program needs to be the correct path to where perl is installed on your server. On all servers, this path is correct:
#!/usr/bin/perl