Workstations cannot connect to server via Remote Desktop Connection

I can map network drives on my workstation to folders on the server (server 2008) but for some reason I can not access the server with a valid user and password through remote desktop connection...I get a message like "computer cant connect to remote computer...." Sometimes I can access the server through remote desktop connection when I connect a laptop to the wireless network...but the workstations just don't seem to want to. It's a strange issue when you consider that the settings for remote desktop allow all connections and I am using xp sp3 on the workstations and the user accounts on the server are set to be used through remote desktop. Any help or advice would be greatly appreciated.

 

Do you have this installed?

http://support.microsoft.com/kb/969084

 

Also, on the server if you don't have the above update, do you have on remote desktop: Allow connections from computers running any version of Remote Desktop (less secure).