Today, I ran across the issue of some Lync clients not being able to connect up to our Lync 2010 server.  They were receiving the following error:

Sign in to Microsoft Lync failed because the service is not available or you may not be connected to the internet.

Turned out this was caused by having an invalid SSL certificate.  The reason the certificate was invalid was this particular Mac was not apart of the domain and therefore the root CA's certificate was not trusted.  Simply importing the root certificate into the keychain logged the user right in.