Grrr...I just spent the better part of an hour debugging what were supposed to be brain-dead simple cgi scripts. The first one failed because I had set the permissions to 777 instead of 755. Apparently Apache can reject scripts that have too much permission without giving a useful error. To me that's like saying you won't accept a general power of attorney because it can be used for evil, but I digress...one chmod 755 later everything was working fine, until...
I moved onto the second, admittedly more complex, script and started getting similar errors. I immediately triple-checked the 755 permissions, but that wasn't it. Turns out there were two errors: the script writer had a space between #! and /usr/lib/perl and my host gave me bad info on the location of sendmail. I spent a good half hour with the script perfectly configured except for the fact that they either moved sendmail or gave me a bad link in the welcome email.
Anyway, it's all better now, and our Church's website now has a simple counter on the home page and a form mail that produces some readble output.