Issue – In the beginning of your Tenant-Creation you have played around with some cloud-only user, you gave them an E1, or E3/4 License or licensed Exchange Online solely. Last but not least, you provide this MSOL-User with a valid smtp alias.
Now, you are stepping forward in project and you establish a Directory Synchronization either with DirSync, AADSync or the soon coming AAD Connect tool. After the sync you realize that in Office 365 still the old username is valid and neither the UserPrincipalName (UPN) or the choosen Alternate Login Name, get used as a new Username for login. Username is still the “old” one -> “whatever@YourTenantName.onmicrosoft.com”
Solution – Even the softmatch is merging your cloud-only ID with the on premises Active Directory Object, you have to change the Username manually in Office 365 with following Powershell Cmdlet:
Set-MsolUserPrincipalName -UserPrincipalName 'Current UPN' -NewUserPrincipalName 'New UPN'