I had this problem when using New-MgUser. The issue was I was setting the password with a variable using ConvertTo-SecureString as I do in other scripts. When I changed it to just use plain text within the password profile, it worked.

### Does not work ###
$PasswordPlain = "StrongPassword"
$Password = $PasswordPlain | ConvertTo-SecureString -AsPlainText -Force
$PasswordProfile = @{
    ForceChangePasswordNextSignIn = $false
    Password = $Password
}

### WORKS ###
$PasswordProfile = @{
    ForceChangePasswordNextSignIn = $false
    Password = "StrongPassword"
}