Exchange 2000/DNS/no outbound mail

We recently changed our entire ip. Everything else seems to be reacting rather well. However, we have no outbound mail. Instead, we are getting “Could not deliver the message in the time limit specified. Please retry or contact your administrator. server.mydomain.com #4.4.7
We are able to recieve mail, just not send. 😐 Please help