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