E-mail Delay

We have recently upgraded our Exchange server from 5.5 to 2003. Users including myself have gotten the followinf message when sending an e-mail to an external address:

“Delivery to the following recipients has been delayed”

If anyone knows how to resolve this issue I would appreciate it.

Thank you.