CalendarScript is not compatible with mod_perl (for now). It's true that you don't necessarily need a "cgi-bin" directory to have perl scripts enabled, though. You can setup your web server to execute perl scripts anywhere.
You just need to tell your web host that you need to run a Perl CGI script _not_ under mod_perl, and they can either tell you exactly what you need to do or tell you that you can't do it anymore 
------------------
Scott
CalendarScript.com