http://support.microsoft.com/kb/2006508

Is someone hosting your Exchange Server? if so, you may want to contact the company hosting it to see if there is an issue on their end, or if your settings are incorrect.