Random accounts locking after global UPN change

I was instructed to change the UPN for users because of O365 migration and Bit Titan.  I tested with my user account chris@newupnA.com and everything seemed to work fine.  I did every user's and now I'm getting a bunch of Kerberos errors like this:

================================================

A Kerberos authentication ticket (TGT) was requested.

Account Information:
      Account Name:            Username@newupnB.com
      Supplied Realm Name:      DOMAINNAME.LOCAL
      User ID:                  NULL SID

Service Information:
      Service Name:            krbtgt/DOMAINNAME.LOCAL
      Service ID:            NULL SID

Network Information:
      Client Address:            ::ffff:10.1.0.182
      Client Port:            57618

Additional Information:
      Ticket Options:            0x40810010
      Result Code:            0x6
      Ticket Encryption Type:      0xFFFFFFFF
      Pre-Authentication Type:      -

Certificate Information:
      Certificate Issuer Name:            
      Certificate Serial Number:      
      Certificate Thumbprint:            

Certificate information is only provided if a certificate was used for pre-authentication.

Pre-authentication types, ticket options, encryption types and result codes are defined in RFC 4120.

================================================

There are 3 new UPNs that are different based off of which department the users are in, but they're all still members of the same domain realm in AD.  It looks like the Kerberos ticket includes the FQDN(with the new UPN) as the authenticating accountname, but is trying to access using the old domain realm.  Obviously this is going to fail..  

Anyone seen this issue before?  

Anyone know if adding the suffix's to Domains and Trusts will fix this and is a smart thing to do?

Any help is welcome.

Thanks in advance!

Chris