@Sigrala ,
Does this error message popup when you sign into Lync 2010 or Lync 2013?
Make sure that you add the following service (SRV) and alias (CNAME) records to your Domain Name System (DNS) host.
For more information about this issue, please refer to this article.
If the response is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.