One of the most likely reason for this error could be in the case that you have been a BPOS customer and you still have Microsoft Sign In Application installed on your PC/laptop.
In this case, Lync probably has picked up the OCS server information from the Sign In application which means the Internal and External server names are pointing to BPOS. You can check this by going to Lync Options:
and in the Personal pane click the Advanced button next to Sign-in address field:
If the connection setting is set to Manual, it is more likely pointing to pool1.oconline.microsoftonline.com:443 which is the address of the Office Communication Server on BPOS.
save the changes and exit the Lync Options.
Now you will need to restart Lync client. Once Lync is restarted, you should be able to log in using your Office 365 credentials without any errors.