Recently we swapped a users UPN on a local domain controller ( which syncs to 365 via AAdconnect) to another domain and SMTP alias, all worked well however she could not login to Skype for Business.
Resetting Windows Credentials, Caches and registry items still would not fix this.
Most of the time this is due to the SIP Address not being correct. Little did we know this user had Lync before migrating to 365 so they had a SIP address in the attribute editor
Changing this resolved the issue