We set up a new domain and migrated all our workstations and the user profiles to the new domain.
We have configured a brand new Exchange server as part of this as well.
We migrated all the profiles using the Profile Migration Tool (which works great)
The only issue we are currently facing is that computers that were on the old domain and migrated to the new one - Exchange autodiscover does not work.
On new PC's that were never on the old domain, Autodiscover works fine. If you are out of the office - autodiscover works.
It seems to only affect the PC's that were on the old domain.
We are using Outlook 2010 with a couple Outlook 2012 as well.