Odd Problem Switching DNS Providers

One of my customers is having an odd problem receiving mail after moving their MX record to another ISP / DNS Host.

The customer has Comcast for business.  Comcast is only being used for the network access.  Their help desk people didn’t know what an MX record was and I decided to have a third party do their DNS.  Their original dial up ISP (prior to switching to Comcast) was hosting their DNS record after they switched to Comcast.  Another company hosts and designs their ecommerce web site.  Their “A” record for their web site and MX record for their internal email server was hosted there.  Everything was working fine.  Mail was being sent and received.

Their current web  provider (not Comcast) also does DNS hosting.  The company decided to simplify things by having their web provider host their DNS information.    They made the changes and got the hand off from the DNS host.  However, after three days since the change they still cannot receive email.

Their mail server can be resolved on the internet.

When I telnet, I get the Exchange server just fine.

Users sending mail to my customer get this error:
The following organization rejected your message: mail88.megamailservers.com.
mail88.megamailservers.com #550 5.7.1 <Administrator@mckeeganequip.com>... Relaying denied: You must check for new mail before sending mail. ##

When I run the test at DNS Report, their network passes all the tests except the “Duplicate MX Records”.  Here is the error:
WARNING: You have duplicate MX records. This means that mailservers may try delivering mail to the same IP more than once. Although technically valid, this is very confusing, and wastes resources. The duplicate MX records are:

mail.mckeeganequip.com. and mail.mckeeganequip.com. both resolve to 70.91.41.238.
mail.mckeeganequip.com. and mail.mckeeganequip.com. both resolve to 70.91.41.238.
mail.mckeeganequip.com. and mail.mckeeganequip.com. both resolve to 70.91.41.238.

They also fail the “Connect to Mail Servers” test:
ERROR: I could not complete a connection to any of your mailservers!

mail.mckeeganequip.com: Timed out [Last data sent: [Did not connect]]
mail.mckeeganequip.com: Timed out [Last data sent: [Did not connect]]
mail.mckeeganequip.com: Timed out [Last data sent: [Did not connect]]

If this is a timeout problem, note that the DNS report only waits about 40 seconds for responses, so your mail *may* work fine in this case but you will need to use testing tools specifically designed for such situations to be certain.

Since email was working fine prior to changing the DNS providers, obviously this is their issue, however they feel that the record is correct and it’s either Comcast or us.

Has anyone seen this before?  What is the best way to resolve this?  

Thanks!!!