I almost broke something, twice! Once figuring out the issue, and the second time when I found the solution.

I had this one machine which refused to connect to another machine via Remote Desktop Connection whereas I could connect via another machine just fine, the credentials were fine.

Turns out RDP was using a different domain, this was a quick fix, look up the Workgroup under System > Properties and enter the username as WORGROUP/USERNAME.

This should fix the pesky issue