From what I've found out, the problem was actually with SELinux policy on Fedora Core 4 (the OS I'm running), which can prevent the execution of the CGIs on apache. This command took care of my issue:
chcon -R system_u:object_r:httpd_sys_script_exec_t /usr/local/nagios/sbin
I found that here:
Thanks to jakkedup for pointing me in the right direction, though I should've thought to go there myself.
Edited Tue Nov 22 2005, 07:33AM ]