Possible reason for this error is if you have not created the DNS records required for Lync Online.
When you add and verify a domain with Office 365, you can choose what services you want to use with the domain. If you choose to run Lunc for the domain, you will need to create two SRV records in the domain's public DNS as below:
which the yourdomain.com should be replaced with the domain you have added and verified with Office 365. Adding above DNS entries will resolve the issue with Lync client.
Some registerars such as 1and1 don't let you create SRV and TXT type records in the DNS. If that is the case, you will need to configure each and every Lync client in your organization to manualy point to Lync Online servers on Office 365.
To do so, open Lync and go to Lync Options:
Click on Advanced button next Sign in Address in the Personal pane:
In the Advanced Connection Settings, change the coniguration setting to manual and change both Internal and External server names to sip.online.lync.com:443. confirm changes and restart Lync.