Ever since the policy to disable TLS 1.0 was pushed down to the local machines, we started getting the error “an authentication error has occurred(code 0x80004005)” when accessing few of our Windows 2008 R2 servers. It was interesting because we have a bunch of other servers with no problems accessing. This seems to be a very generic error code as google results were showing multiple problems and multiple solutions for this.
Apparently, in my case, the patch to add RDS support for TLS 1.1 and TLS 1.2 was not installed in 3 of the servers with this problem. So I had to download the patch from this Microsoft website and install and reboot them remotely. Once installed and rebooted, voila!!
Edit: There are multiple reasons for this problem, and there are multiple ways to fix it. I am just sharing what worked for me, and it may not work for all. Saying this because this post is now in the first page of google results and I am getting lot of traffic to this, and I do not want to disappoint you. Thanks