Fedora ships with SELinux (Security Enhanced Linux) installed and in Enforcing mode by default. This can result in "Internal Server Error" messages when you attempt to access or install software.
See if SELinux is in Enforcing mode.
Put SELinux into Permissive mode.
# setenforce 0
The Nagios CGIs should work now. To make this change permanent, you'll have to modify /etc/selinux/config.