Check your nagios.cfg file.
RETAIN STATE INFORMATION
This setting determines whether or not Nagios will save state
information for services and hosts before it shuts down. Upon
startup Nagios will reload all saved service and host state
information before starting to monitor. This is useful for
maintaining long-term data on state statistics, etc, but will
slow Nagios down a bit when it (re)starts. Since its only
a one-time penalty, I think its well worth the additional
STATE RETENTION FILE
This is the file that Nagios should use to store host and
service state information before it shuts down. The state
information in this file is also read immediately prior to
starting to monitor the network when Nagios is restarted.
This file is used only if the preserve_state_information
variable is set to 1.
RETENTION DATA UPDATE INTERVAL
This setting determines how often (in minutes) that Nagios
will automatically save retention data during normal operation.
If you set this value to 0, Nagios will not save retention
data at regular interval, but it will still save retention
data before shutting down or restarting. If you have disabled
state retention, this option has no effect.
USE RETAINED PROGRAM STATE
This setting determines whether or not Nagios will set
program status variables based on the values saved in the
retention file. If you want to use retained program status
information, set this value to 1. If not, set this value
To fix the "service down/no notifications sent" problem, clik the link called "Enable notifications for this service" for the service(s) that you wish to have notifications sent.
I know that sounds weird, since you have notifications enabled in your config files, but it has to be done. I'm not sure why, and it's a common question and bugged me for weeks. If the link isn't there, but the disable link is, disable, then enable, and you will be good to go.