Cannot send message after changing DNS

[UTTech]

Small Business Server 2000
Exchange 2000

We just changed our ISP and changed DNS. After the change, we cannot send any messages and receive the following system administrator message:

You do not have permission to send to this recipient. This system is not configured to relay mail from <username@domain.com> to <username@domain.com> for xxx.xx.xx.xxx.

The IP address it is resolving to is the old DNS. Please help!!

 

[tmt7734]

How long ago is just? It can take up to 72 hours for DNS to replicate.

 

[UTTech]

I did it 5pm on Friday.

I just realized that the IP address is our public address, not the old DNS.