I had a problem with a hard drive on a Dell Dimension 4300 pc so I had to install a new drive and start from a fresh install, no biggie. However, after installing some windows updates AFTER SP3 (meaning RDP worked fine just after installing SP3) Remote Desktop will not work unless I have logged in to the machine locally (sitting at it and pressing Ctrl-Alt-Del from its own keyboard).
It was working and now it isn't. I have read some posts saying its the video card but I have the latest driver for an obsolete card (ATI Rage 280 Ultra) and that did not fix it either.
Once logged on locally I can use remote desktop.