Remote Desktop - Can't connect to remote machine from only 1 of my 3 work machines

Question

I'm having an issue connecting to a remote machine (Win Server 2012) using Remote Desktop.. but the weird thing is I only have trouble connecting from one machine that I use. I can connect from two other machines fine, even with the same credentials. From the problem machine (Windows 7), I am given a login prompt before seeing the error pictured at the end of the post. I can remote to several other servers from the problem machine without issue.

Things I've tried so far:

1. Connecting to the remote machine using the fully qualified domain name
2. Connecting to the remote machine using the IP address
3. Logging in to the remote machine with the system administrator account
4. Switching the problem machine IP to static and setting it to a known IP address from a "good" machine
5. Deleting the default.rdp file in My Documents on the problem machine
6. Checked everything in this help article... most of this stuff can be eliminated automatically because many other machines can connect. I did however double check Windows Firewall on both my machine and the server, as well the Network Level Auth settings on my machine.
7. Checked the remote machine's Event Viewer logs. Nothing to be found in the log immediately after a failed connect attempt from the problem machine

Again... I can connect to this server just fine with my credentials on two other client machines (one is Windows 7, one is Windows 8.1). What am I missing here?? What else can I try to figure this out?

The error:

EDIT

Group policy settings on the server:

The only thing that is configured is the Network Level Auth requirement, which I confirmed on the "problem" machine by following steps in my above linked help article.

Solution

Since it's a Windows 2012 machine you are trying to remote into using a Windows 7 PC, it might be that you don't have all the necessary Windows Updates for TLS 1.1 & TLS 1.2.

Try installing this Windows Update (KB3080079)

Then restart your PC and attempt to initialize the remote desktop connection.

Comments

[Tonny]

Are you sure the 1 problem machine isn't blocked by a firewall rule on the server ? What happens if you try to ping the server from the problem machine?

[Borophyll]

@Tonny ping works from the problem machine

[Kamil Maciorowski]

Is MTU the same on three connecting machines? Try lower MTU on that specific one.

[Tonny]

@KamilMaciorowski That would be a really special edge case if the MTU makes the difference. That would imply a mis-configured router between the problem machine and the server causing fragging issues. (RDP is always TCP, so should be fraggable under normal circumstances.) It's worth a try though....

[Borophyll]

@KamilMaciorowski I tried changing the MTU from 1500 to 1458 as well as 1430 - still not working

[Borophyll]

I don't think Remote Desktop Session Host Configuration exists on Server 2012... I looked at the alternative listed in the article (group policies) and none of them appear to be configured. See edit to main post for a screenshot of those group policies

[Borophyll]

Bingo - this machine had issues with Windows Update a long time ago, downloading this individual update solved the problem.