"Your Credentials Did Not Work" on connect, but remoting into another machine first works

Question

I'm trying to remote desktop into a win7 pro desktop across VPN. When I try to connect I get an error saying

Your credentials did not work.
The credentials that were used to connect to [computer] did not work. Please enter new credentials.

If I remote into a server on the network, I can then remote desktop into the desktop machine (doubly remote desktop).

• Username (with domain) and password were first typed into notepad then copy/paste for every remote desktop session.
• Clocks in the taskbar are the same, within 60 seconds, accounting for time zone change.
• Issue is the same using both computer name and IP address.
• edit: "Allow connections from computers running any version of Remote Desktop" is (always was) checked on the computer I'm trying to remote into.
• edit: I can access a fileshare on the machine I'm trying to remote into yet remote desktop still fails.

Picture to help clarify the issue:

edit (Dec 2015):

We bought a new (local) router and the issue seems to have resolved itself.

---

Can't connect to remote desktop via Cisco VPN using wireless connection, works with wired did not help

Answer 1

I believe the Win7 computer has NLA enabled and because you are on a non-domain-joined machine, you are not able to access it (while the 2008R2 does not have this). You can read more here: https://technet.microsoft.com/en-us/magazine/hh750380.aspx