If you have problem with the contact lists of Lync 2013/Skype for Business 2015 client, be sure to verify that the user that has problem is not configured to use the UCS (Universal Contact Store) if you don’t want to use it.
To disable it, from powershell digit the following:
Invoke-CsUcsRollback -Identity identityoftheuser
In this way you can revert back to use the Skype For Business contact list.
To check which provider the client are using press the Control and right click on the skype for business icon on the notification area of windows and select Configuration Information. Check the “Contact List Provider” row.