If you have activated Skill search in Skype for Business or Lync 2013 and you get instead an error ""An error occured during search.Please try again, and contact your support team if the problem continues" .
Using IIS log on Sharepoint you may see that there is en error 500
2016-05-13 15:05:24 192.168.254.12 POST /_vti_bin/search.asmx - 443 - 192.168.254.182 OC/15.0.4809.1000+(Skype+for+Business) 500 0 0 78
From the client side you may see this issue in Fiddler.
Try to check if Anonymous Authentication is activated for _vti_bin folder. Open IIS, sites - SharePoint -80 or whatever you have there, find _vti_bin and disable Anonymous Authentication.
SfB will use Windows Authentification to get there. Checkout for side effects if some applications or hackers prefer to use anonymous authentification - that will not work anymore.
Another thing here is that if you have enabled Kerberor authentification might work ok without any change.
Not that _vti_bin is deprecated method - plan to stop using it in the future.
Most probably this will be changed in SfB client rather soon.