Le motivazioni possono essere diverse.
1. errata configurazione del webserver (il webserver deve sapere che in quella dir ci possono stare degli esegubili e che tali eseguibili possono essere richimati da web;
2. errate permssion alla dir o ai file contenuti (i file CGI devono essere 755, la dir pure - mi pare);
3. errata intestazione degli eseguibili (la prima riga del file deve essere in formato testo e linkare l'eseguibile che interpreta il Perl);
4. ...

Ulteriori info per tutti questi punti li trovi (fra l'altro) sul sito di shishii.