When you say "changed server DNS" do you mean you made a change to the DNS record or changed the DNS resolvers your server is pointing to?

If you changed the MX record for the zone involved, it could take time to propigate based on the TTL in the record and your NT server could be sending to the wrong MX host.

Double check your name resolution with nslookup via the command line and make sure that the server is pointing to the correct resolvers and they are returning the MX record you expect.