It would seem that your DNS and MX records are set correctly, and propagated.
It would appear that your server is not responding to incoming connections. This is not a problem in Mercury's domain settings, as it does not get to the point of checking them.
Are you, by any chance, running Windows XP with SP2 installed? If so, have you opened up port 25 on the firewall to allow incoming connections?
If not, what OS are you running, and what, if any, firewall programs are you using?