We had a silmilar problem and it had to do with a microsoft update on the users machines...if you use Windows Firewall (even if you don't ) check this first, the update wiped out all of our exceptions so Remote desktop and File sharing was disabled. You may want to start there, I cannot remember what update it was but re-checking the exceptions Remote Desktop and File Sharing worked.