RDP Clients unable to connect

Hmmm... a couple of things you can do here..

Firstly, you may have a failure to locate/communicate between your TS Server and the TS Licensing Instance.  The TS server will try to contact the Licensing server on port 135, which is normally open on a DC - or it wouldn't be functioning as a DC...  So it's more likely that it's a "locating" problem.  You can specify where the TS server should look for the TS Licensing Instance by specifying it in the TS Configuration Tool (AdminTools:TerminalServices:TerminalServicesConfiguration).
Other troubleshooting options are here:
http://technet.microsoft.com/en-us/library/cc758805(WS.10).aspx


Another option is to "whack" the temp key off the client workstations to see if that gets you by, although the problem will reappear in 90-120 days...  
http://support.microsoft.com/kb/187614

Forgot to mention...
- Make sure the TS Licensing mode matches the TS Licenses that are installed on the TS License server (Per Device vs. Per User).
- Make sure you've got Firewall turned down on your DC...

Scooter, thanks for the help. On the Terninal Server itself, in TSAdmin I had already specified my license server under the "License Server Discovery Mode" entry & my licensing Mode is per Device & that does match the 155 DEV CAL's that I have registered with my TS License Server. The Domain Controller's do not have any software firewalls on them, so that shouldn't be a factor in this.

I also looked at the KB article that you have posted above, but it does not cover Windows XP Pro, which is the OS of the PC's having this issue. Oddly enough, they do have a Vista Ultimate machine @ that problem location & it can connect fine, but the XP Pro machines cannot! Don't know what that is all about., but that may shed some light on this issue. but the article did have some interesting info... According to it, a temp license is issued to clients connecting, once they disconnect they still have a temp license, but upon a succesful 2nd connection the license goes from temp to a regular DEV CAL.. I have 3 temp licenses in my RDP Licensing Server, & all 3 are for the 3 troubled machines at that location. I agree, there is a communication problem somewhere but I can't find it! The gentleman at the other location did try & blow out the registry keys, I can only assume it went through the same steps the above article was getting at, only for XP Pro. Thanks again for your help!

How about the RDP client version on the XP boxes?
Also could check on the 2008 server to see what level of security it's running (Network Level Authentication):
  - Go to System Properties & "Remote" tab.
  - Check Security option "Allow connections... running any version of Remote Desktop (less secure).

Also, are you running TS Gateway Services or have it installed??  If you do & are not using it - remove it.  It'll add on a fair bit of security (TS-RAP & TS-CAP policies) that could prevent connections...

The guy on the remote end updated the RDP client on his XP machine to the newest version, but the results remained the same, nothing changed. My RDP & licensing servers are both Windows Server 2003 Std. Ed., so there is no "Network Authentication" area in my System Properties under the remote tab, unless I'm missing it. & There was no TS Gateway Services installed when this was setup. I don't see anything on either server that indicates TS Gateway Services is there.