Exchange 5.5 Problem`

I am suddenly having problems with Exchange 5.5. I installed Windows updates on Thursday Aug 21st. Now I can receive mail in, however when we send mail out I get the following response almost immediately:

Your message did not reach some or all of the intended recipents.

Subject: TEST
Sent: 8/25/2003 3:32 PM

The following recipient(s) could not be reached :

‘someone@somwhere.com’ on 8/25/2003 3:32 PM
The recipient name is not recognized
The MTS-ID of the original message is :

I thought it might me the DNS but all of the internet sites are working for us. Any help is greatly appreciated.