After we moved one of our user mailboxes from Exchange 2003 to 2010, the user started getting a Cannot get mail. The connection to the server failed error message on their iPhone device.

There are a lot of references on Google to check for inherited permissions to resolve the error message.  We quickly determined that we were not dealing with a permissions issue.

After some additional troubleshooting and research, we were able to isolate the problem to a device partnership issue.

To resolve the issue, use ADSI Edit to find the user object.

When you find the user object, double-click on it and you should see a CN=ExchangeActiveSyncDevices container under the user object as shown below.  On the right-hand side, you should see one or more device partnerships.

 

Right-click the device partnership according to the device the user is using, and click Delete.

After you remove the device partnership, please wait until Active Directory replication completes before you set up the device again.