Changing the IP on an Exchange 2k domain

We are loosing a stack of IP’s from ATT this week and one of those happens to be our main Exchange 5.5 server’s WAN IP. We tryed changing the IP of the NIC and also the MX record to point the new IP, but after doing that, no one is able get thier mail.

Anyone have any idea what is causing this?
We can change the IP back to th eoriginal and it continues to work fine.