Lync 2010/2013 stores credentials when you initially set it up. This might lead to connection issues after resetting password.

Here are the steps to fix the issue (close Lync first):

Remove the certificate

  1. Go to Internet Explorer > Tools > Internet Options > ContentCertificates
  2. Remove the certificate issued by Communication Server under Personal > Certificates
    Lync Certificate

Clear entries in Credential Manager

  1. Go to Start > Control Panel > Credential Manager > Windows Credentials > Generic Credentials
  2. Remove the entry with the following address: Microsoft_OC1:uri=username@domain.com:specific:*
    Credential Manager

Remove Crypto folder

  1. Go to %System_Drive%\ProgramData\Microsoft\Crypto\RSA
  2. Remove the folder S-1-5-*

Set the Communicator registry key to disable saving password

  1. Go to Registry Editor (Start > Run > regedit > OK)
  2. Choose HKEY_CURRENT_USER\Software\Microsoft\Communicator
  3. Double-click the value SavePassword and set it to 0
    regedit

After following all the steps run Lync again and enter correct credentials.