I had this one too.. easy to fix. You're right, Nagios is probably running, there is a setting you need to change to allow Nagios to actually check that itself is running...!
Its an entry you need to change in the cgi.cfg file. Just uncomment the line that starts nagios_check_command= save the file, you may need to restart nagios if this doesn`t fix the prob.
The link below should will give you further info.
http://nagios.org/faqs/viewfaq.php?faq_id=170
Hope it fixes your problem.