I've actually just resolved this issue for myself - I had been struggling with it for weeks.
Basically my remote desktop used to work, but suddenly stopped, and I could not figure out how to get it going again. In my set up, I am using a laptop to try connect to a desktop located somewhere else in the building but on the same network. All the Remote Desktop configurations were in place it seemed.
So after reading a post above suggesting looking at the Remote settings under My Computer (My Computer, Right Click, Properties, Remote) I notice that you could add users specifically that can access this computer remotely. It said that my user was already configured to access the machine remotely, but I went ahead and added myself anyway, and as soon as I did, voila!! (as they say)