I do not believe mismatched NLA would affect an RDP connection in this way. I've only seen that effect when trying to authenticate shares and the like.
Are you getting the error once you're at the logon screen on the remote server, or from the RDP credentials dialog on your local screen?
One possible reason could be that the account is configured not to allow the user to change their own password. I've seen this configuration several times in environments where smart cards logins are only partially implemented. Users are configured to allow smart card authentication, but not require it. So, there is a password associated with the account, but the user has no knowledge of (or control over in some cases) the password - which may or may not have been reset as a part of the smart card implementation.