Strange RDP / Remote Desktop problem

I'll try to be as specific as I can be:

• Server is running SBS 2008 R2 (with all updates)
• Server is connected to the internet
• Server has 2 NIC's, one is disabled
• Server is running RDP Service (accessible directly from the internet, I know, not as secure as it should be)
• Computers A and B are on the same local net.
• Computers A and B are both Windows 7.
• Users X and Y are both admins on the server
• Computer A can connect as user X to the server with mstsc
• Computer A can connect as user Y to the server with mstsc
• Computer B can connect as user X to the server with mstsc
• Computer B CANNOT connect as user Y to the server with mstsc! Error that username/password is incorrect.

The last point is the problem, I get an authentication error. This used to work flawlessly for the last year. The server and desktops have been rebooted.

EDIT:

I tried:

• prefixing domain to the username
• prefixing the server computer name to the username
• change the password
• copy/paste the password from notepad to make sure it was correct

I find it very strange....

EDIT:

• The computers are not on the same subnet as the server. The server is at my hosting provider.
• All computers as all users can reach the web app that is running on the server.

I was having this exact same issue. All I did was log into the local administrator account via RDP, logged out, and all users were fixed.

The local administrator account did NOT have an active session after a server reboot. Very strange.