WE HAD THE SIMILAR INSTANCE WHEN I CHANGED EXCHANGE SERVER (NEW SERVER SAME NAME)ABOUT A YEAR AND A HALF AGO. PEOPLE COULD NOT LOG IN WHAT WE FOUND IS IF YOU DELETED THE LAST CHARACTER IN OUR EXCHANGE SERVERS NAME AND THEN ADDED THE CHARACTER BACK AND THEN DID A CHECK NAME ALL WAS FINE. YOU MIGHT WANT TO TRY THIS. STILL ALOT OF WORK BUT WAS EASIER THAN RECRAETING THE WHOLE PROFILE.