Issue

When the user object is being synced to the cloud service, you receive the following error message in the synchronization error report:
Unable to update this object in Microsoft Online Services, because the attribute FederatedUser.UserPrincipalName is not valid. Update the value in your local Active Directory

Solution

The corresponding support article from Microsoft describes the error and provides a working solution. However, its two steps, depends on inputting the tenancy domain and does not provide any error checking.
With the Azure AD module it is necessary to set a password profile. The function imports the system.web assembly to generate a random password on the fly. Don't Panic! The users password will be synced once changed to the federated domain.

High Level Steps:
  1. Capture the Azure AD User.
  2. Create the Password Profile for temporary password.
  3. Build the non-federated domain from the tenancy domain.
  4. Set the UserPrincipalName to the non-federated domain.
  5. Set the UserPrincipalName to the Active Directory federated domain.
  6. Show some output.
Code:

#Requires -Module AzureAD
Function Update-xAzureADUserUserPrincipalName {
    <#
.SYNOPSIS
    Uses Set-AzureADUser cmdlet to update the users UserPrincipalName to a non-federated domain and then to the correct
    UserPrincipalName after receiving error: Unable to update this object in Microsoft Online Services, because the
    attribute FederatedUser.UserPrincipalName is not valid. Update the value in your local Active Directory.

.DESCRIPTION
    When a users UserPrincipalName is updated within Active Directory, AAD Connect does not replicate the change.
    In order to update the change in Azure AD the UserPrincipalName must INTIALLY be set to a non-federated domain.

    The tenancy domain represents a non-federated domain and importantly CANNOT be federated. This function performs
    this two step process to update the users UserPrincipalName to reflect the change in Active Directory.

    With the Azure AD module it is necessary to set a password profile. The function imports the system.web assembly
    to generate a random password on the fly. Don't Panic! The users password will be synced once changed to the
    federated domain.

.EXAMPLE
    This example updates user Fakey McFakerson's UPN from [email protected] to [email protected]

    Update-xAzureADUserUserPrincipalName -UserPrincipalName [email protected] -NewUserPrincipalName [email protected]

.NOTES
    AUTHOR   : Steve Rackham
    BLOG     : https://siliconwolf.net
    GIT      : https://github.com/siliconWOLF
    TWITTER  : https://twitter.com/siliconW0LF
    LINKEDIN : https://nz.linkedin.com/in/steverackham
    TO-DO    : Add pipeline support and Azure AD user object support.

#>

    [CmdletBinding(
        HelpUri = 'https://docs.microsoft.com/en-us/powershell/module/azuread/set-azureaduser?view=azureadps-2.0'
    )]
    param (
        [Parameter (
            Mandatory,
            HelpMessage = "Enter the old UserPrincipalName (UPN)"
        )]
        [MailAddress]$UserPrincipalName,

        [Parameter (
            Mandatory,
            HelpMessage = "Enter the current UserPrincipalName in Active Directory"
        )]
        [MailAddress]$NewUserPrincipalName,

        [Parameter(
            HelpMessage = "Enter the UsageLocation (EG: NZ)"
        )]
        [String]$UsageLocation = "NZ",

        [Parameter(
            HelpMessage = "Enter delay (in seconds)"
        )]
        [int]$Delay = 5

    ) # END PARAM

    # Offset for Verbose/Output stream formatting.
    $OffSet = 0 - $UserPrincipalName.Length

    # GET AZURE AD USER: ------------------------------------------------------
    try {
        Write-Verbose ("{0, $OffSet} : {1}" -f "[ $UserPrincipalName) ]", "Capturing Object ID for reference...")
        $AzureADUser = Get-AzureADUser -ObjectId $UserPrincipalName -ErrorAction Stop

    }
    catch {
        Write-Warning ("{0, $OffSet} : {1}" -f "[ $UserPrincipalName ]", "$($Error[0].Exception.Message)")
        Return

    } # END TRY/CATCH

    # CREATE PASSWORD PROFILE: ------------------------------------------------
    #  IMPORTANT! MAX 15 CHARS! This is a limitation within Office 365 as of writing.
    Write-Verbose ("{0,$OffSet} : {1}" -f "[ $($AzureADUser.ObjectID) ]", "Creating Password Profile...")
    $PasswordProfile = New-Object -TypeName Microsoft.Open.AzureAD.Model.PasswordProfile

    # Generate a password and capture to the password profile password value.
    # NB: (10, 5) translates to 10 alphanumeric and 5 non-alphanumeric characters.
    Add-Type -AssemblyName System.Web
    $PasswordProfile.Password = [System.Web.Security.Membership]::GeneratePassword(10, 5)
    Write-Debug ("{0,$OffSet} : {1}" -f "[ $($AzureADUser.ObjectID) ]", "Password: $($PasswordProfile.Password)")

    # NON FEDERATED DOMAIN: ---------------------------------------------------
    # Build the UPN suffix from the tenancy domain. This makes it portable against other tenancies without
    # hardcoding.
    $tenantDomain = (Get-AzureADTenantDetail).VerifieDDomains   |
        Where-Object {$_._Default -EQ $true }                   |
        Select-Object Name

    $NonFederatedUPN = ($AzureADUser.UserprincipalName -split '@')[0] + '@' + $tenantDomain.Name

    # SET OPERATION: ----------------------------------------------------------
    # First to non-federated domain.
    try {
        Write-Verbose ("{0,$OffSet} : {1}" -f "[ $($AzureADUser.ObjectID) ]", "Setting UPN: $NonFederatedUPN ...")
        Set-AzureADUser -ObjectId $AzureADUser.ObjectId -UserPrincipalName $NonFederatedUPN -PasswordProfile $PasswordProfile -ErrorAction Stop

    }
    catch {
        Write-Warning ("{0, $OffSet} : {1}" -f "[ $($AzureADUser.ObjectID) ]", "$($Error[0].Exception.Message)")

    } # END TRY/CATCH

    # Add a delay. It should be fine but sometimes cloud can be finicky.
    Write-Verbose ("{0,$OffSet} : {1}" -f "[ $($AzureADUser.ObjectID) ]", "Delay for $Delay seconds... Because Cloud...")
    $i = 0
    do {
        Write-Progress -Activity Waiting -SecondsRemaining ($delay - $i) -PercentComplete ($i / $Delay * 100)
        Start-Sleep -Seconds 1
        $i++

    } until ($i -eq $Delay) # END  until ($i -eq $Delay)

    # SET OPERATION: ----------------------------------------------------------
    # And to the correct userprincipalname.
    try {
        Write-Verbose ("{0,$OffSet} : {1}" -f "[ $($AzureADUser.ObjectID) ]", "Setting UPN: $NewUserPrincipalName ...")
        Set-AzureADUser -ObjectId $AzureADUser.ObjectId -UserPrincipalName $NewUserPrincipalName -ErrorAction Stop

        # Capture the user again for reporting.
        $AzureADUser = Get-AzureADUser -ObjectId $NewUserPrincipalName -ErrorAction Stop

    }
    catch {
        Write-Warning $Error[0].Exception.Message

    } # END-TRY/CATCH

    # OUTPUT: ----------------------------------------------------------------
    if ($NewUserPrincipalName -eq $AzureADUser.UserPrincipalName) {
        Write-Output ("{0,$OffSet} : {1}" -f "[ $($AzureADUser.ObjectID) ]", "Update Successful : $($AzureADUser.UserPrincipalName) ")
    }
    else {
        Write-Output ("{0,$OffSet} : {1}" -f "[ $($AzureADUser.ObjectID) ]", "Update Error : $($AzureADUser.UserPrincipalName) ")
    }

} # END-FUNCTION: Update-xAzureADUserUserPrincipalName #######################

Happy Coding...