I have an Exchange 2010 hybrid environment with dirsync, no ADFS.  

Everything seems to be working on the exchange side.   I can transfer mailboxes to and from the cloud, etc.  

We do not have a Lync server, but are able to connect to lync online from our local network without issue.    Connecting to Lync from a mobile device (Android only tested so far) has been giving some strange and inconsistent problems.   Sometimes it tells you you can't connect to the server,  sometimes it logs you into lync allows you to use the app, and then tells you your exchange credentials aren't valid.   

Using the remote connectivity analyzer, our lync DNS settings all show green, but the connectivity test fails with:

I've been unable to figure out the issue.   The only thing I can think of is that we have a wildcard cert on our exchange server.  I'm not sure if that would be the cause or what the solution would be if it is.

Hi,

From your description above, it can be the issue of the authentication. Please double check the authentication on Lync Online side.

Here is a similar case may help you:

http://community.office365.com/en-us/f/613/t/240882.aspx

If the issue persists, as the forum you posted is for Lync Server On Premise only. The issue is more related to Lync online, you can also post a question on Office365 forum for assistance. Thank you for your understanding.

http://community.office365.com/en-us/f/166.aspx

Best Regards,
Eason Huang