Ensure that your Microsoft Exchange Autodiscover is setup correctly.

The Autodiscover feature in Microsoft Exchange provides the mail client with configuration options and shares only the user's email address and password. This is useful for remote users and smartphone users who do not want to enter advanced settings like server names and domains. It is also required for the correct functioning of features such as out of office and the offline address book in Microsoft Outlook.

Use EWSEditor to test if there are any doubts. For more information, see KB 40351.