If you get login problem in Skype Online the first thing is to check if the user has the correct license.
If the user still have problem to log in, I would recommend to run power shell command to see the properties for that specific user.
Get-CsOnlineUser -Identity firstname.lastname@example.org | fl SipAddress,DisplayName, OnPremHostingProvider, Enabled
In this scenario you will see that the user is disabled and also OnPremHostingProvider = SRV
This can happens if you have an old On-Prem solution.
In local Active Directory you will see "msRTCSIP-DeploymentLocator" = SRV.
Click on Clear
Wait for Directory Sync from Active Directory to Azure AD
After DirSync the user is automatically enabled