An easy way to test firewall/listener daemon issues like this is to run "telnet host 25". You should get a prompt something like this:
user@host $ telnet mailhost 25
Connected to mailhost.
Escape character is '^]'.
220 mailhost.maildomain ESMTP Sendmail 8.13.1/8.13.1; Mon, 31 Aug 2009 16:19:30 -0700
If you don't, either the server is down, or it is refusing connections on that port. Actually, it's a great test for lots of port/FW issues (just telnet host port). I use it regularly when testing FW rules.