You need to check your /var/log/chkservd.log and see if it shows why the check is failing. chkservd attempts a connection to port 25 and looks for the 220 response code. You can try this yourself:
telnet localhost 25
It should reply with something like:
Connected to localhost (127.0.0.1).
Escape character is '^]'.
220-homer.webumake.net ESMTP Exim 4.66 #1 Mon, 16 Jul 2007 10:21:13 +0100
220-We do not authorize the use of this system to transport unsolicited,
220 and/or bulk e-mail.
If it doesn't, then that's a problem. If it does, try disabling ASSP (which interferes with the SMTP connections into your SMTP server) and see if the issue improves.