Had the same issue
Solution for me:
If you're on a domain, use the full server name to connect to, like: servername.domain.local
Just 'servername' won't work even if it resolves fine
I assume this has to do with Kerberos authentication in the domain and NTLM being disabled on the domain
Needs FQDN to do auth
Sad to see admins still enabling NTLM or bypassing other security measures to get it working
Even worse is people not disabling the setting in GUI (remote logon settings > uncheck 'Network Level Auth'), because it is not secure, but then running the powershell script to disable exactly that.
GL HF