After a local server maintenance, my Galaxy Nexus (Android 4.1.1) stopped connecting to the Exchange Server.
I removed the account to try re-adding the account and doing so lost all my emails, calendar and contacts.

No matter how hard I tried, I could not add my account “wind\jason.bickley”.
I always received the error “Could not connect to the server”.

However, when I tried puting in an intern’s credentials it could connect.
Our I.T. Manager then found the following solution and corrected it in Active Directory.

http://technet.microsoft.com/en-us/library/dd439375(EXCHG.80).aspx

“In Exchange Server 2010, you may also experience this issue if the Exchange Servers group does not have the appropriate permission to the mailbox object in Active Directory. The most common cause for this is broken Access Control List (ACL) inheritance in Active Directory.”

To check whether inheritance is disabled on the user:

1. Open Active Directory Users and Computers.
2. On the menu at the top of the console, click View > Advanced Features.
3. Locate and right-click the mailbox account in the console, and then click Properties.
4. Click the Security tab.
5. Click Advanced.
6. Make sure that the check box for “Include inheritable permissions from this object’s parent” is selected.

If the user is a member of certain protected groups such as Domain Administrators, it is normal for this box to be unchecked. If you are experiencing a problem with members of these protected groups you should check the permissions on the AdminSDHolder object.”