This is yet another fine Microsoft Office365 related article. I guess by now you've realized we just went through an upgrade from Microsoft's BPOS implementation of hosted Exchange to Office365. For the upgrade Microsoft gives us administrators a checklist of things one needs to do before the transition to make things work. Let me be the first to say that the section on moving from Office Communicator to Lync 2010 is bull shit!
Anyway, after the forced upgrade to Office365 we noticed that over 75% of our users could not sign-in to Lync 2010. If they tried they would get an error saying:
The user name, password, or domain appears to be incorrect. Ensure that you entered them correctly. If the problem continues, please contact your support team.
Now I know what you are thinking, it sounds like a simple bad password issue right? Not so easy their hot shot. The same users can login to Outlook and the Office 365 portal with their credentials just fine. We contact Microsoft support, and they had us try some stuff like applying a hotfix, or checking for old certificates, but nothing worked. That is, nothing except removing Lync for each user, waiting for an hour, then re-adding Lync to each user's account.
To do that in the admin portal for Office 365, go to users. Click on the affected user, then uncheck Lync and save the config. Wait about an hour for it to sync with the Lync servers, then re-check that box and save it again. Same thing, wait an hour and have the user try to login.
Simple right? Why this isn't in Microsoft's knowlege base I have no idea, but it works.