CGI scripts will not run when permissions set to 777. You may set permissions to 777 on folders, but the calendar.pl file's permissions should be set to 755 (this also goes for calendar_admin.pl & debug.pl). See if that works.
Below are some other things that I found help.
Checklist:
1. All calendar files uploaded in ASCII mode.
2. Be sure your FTP program does not change any data when you are uploading (I had one that changed tabs to spaces and created a 500 problem).
3. Check with web host and be sure you have the correct pearl version (on server) and path (1st line in .pl files). Also be sure server can run .pl files (on some servers you may need to change the .pl to .cgi in order to have it run. This change may also require changes in the config files or the calendarscript.)
4. Be sure if you are using the BASE_DIR that it is the correct file path (this is different from the HTTP path).
Hope some of this helps,
Jason