Issues with new email alias/domain in Exchange Hybrid environment

Hi,

We have a working hybrid Exchange Online setup which is working fine for all users with our original email address. We recently purchased and new email domain and want to move two users to that domain. The problem is, after changing the user's UPN to the new domain for sign in, the user is constantly getting prompted for user credentials in Outlook. 

What has been done:

• New email domain has been properly setup in Azure 
• Email domain added as an additional UPN in Active Directory
• Users UPN has been changed to the new UPN
• User default email address has been changed to the new domain
• Appropriate MX and DNS records have been created

Is there anything else in Active Directory that I should be doing that I'm missing?

Regards 

Paul