"Active Directory operation failed on "domain controller
". You cannot retry this operation: "Insufficient access rights to perform the operation"
What do you mean I don't have rights, I'm a Domain Admin for crying out loud!!!! So onto the troubleshooting my rights. I have rights in AD. Lync server can contact the domain no problem. Everything looked to be fine. Then I found that my user account was in a "Protected Security Group" by being a domain admin.
Due to some security features in Active Directory (explained here), when you add or make a change to a user that is in a "Protected Security Group" (i.e. Enterprise or Domain Admins) in Lync 2010, you have to change their security to:
"Include inheritable permissions from this object's parent"
Steps to change this setting: