Terminal Server 2008 client access problem

I have a Domain that runs a server2003 Terminal Server - no issues with this. Recently I installed a second TS with server2008 installed. The TS Licensing role was transfered to the new TS. Several computers on the Domain are unable to log on to a TS session on the new server however. The error I get is as follows -

"Because of a security error, the client could not connect to the remote computer. Verify that you are connected to the network, and then try connecting again."

This is Client Computer dependent - Some computers are OK and I can log onto a TS session with any user account but on the computers with the problem I cannot log onto a TS session no matter what user account I try. I can still log onto a TS session on the old terminal server from all client computers though.

I have been through the obvious settings, rebooted the server and clients etc but the problem remains still. I cannot see anything in the system logs of either the client or the server that might be related.

I am out of ideas and would appreciate any help being offered on this.