This error may occur if your local computer is joined to a domain, however, the RDP server you are connecting to is not on the same domain (or not on a domain at all).

If you send the username as simply: User

Your local system will essentially send it as: LocalDomain\User

This will fail to authenticate properly unless the RDP server is a member of LocalDomain.

To get around this, all you need to do is specify your user as: .\User

This ensures any domain is not sent as part of the authentication.