From Debian package 0.0.20080702-10
In russell-20080929.diff

Update Debian nagios paths
Fixes Debian bug #493979

Index: policy/modules/services/nagios.fc
===================================================================
--- policy/modules/services/nagios.fc.orig
+++ policy/modules/services/nagios.fc
@@ -17,9 +17,12 @@
 /var/spool/nagios(/.*)?					gen_context(system_u:object_r:nagios_spool_t,s0)
 
 ifdef(`distro_debian',`
-/usr/sbin/nagios				--	gen_context(system_u:object_r:nagios_exec_t,s0)
-')
+/usr/sbin/nagios.*				--	gen_context(system_u:object_r:nagios_exec_t,s0)
+/usr/lib/cgi-bin/nagios.?/.+			--	gen_context(system_u:object_r:nagios_cgi_exec_t,s0)
+/usr/lib/nagios3/cgi/.+			--	gen_context(system_u:object_r:nagios_cgi_exec_t,s0)
+', `
 /usr/lib(64)?/cgi-bin/nagios(/.+)?			gen_context(system_u:object_r:httpd_nagios_script_exec_t,s0)
+')
 /usr/lib(64)?/nagios/cgi-bin(/.*)?			gen_context(system_u:object_r:httpd_nagios_script_exec_t,s0)
 
 # admin plugins