While adding or deleting a contact in Lync client, you receive this error.
This message appears if
- UCS is enabled for user and the contacts are on Exchange server
- Bad SIP cache data
If the user is enabled for UCS, by running Invoke-CsUcsRollback command, which will migrate contacts to Lync server (remember not to use -Force switch which will result is contact loss for that user). Once the contacts are migrated to Lync server, the user will be able to add/remove contacts in Lync client.
You may also delete SIP cache and try adding contacts.