Error al conectarme por Terminal Server

Hola!!

Nos hemos encontrado con un problema bastante extraño. Os comento.
Tenemos una granja de servidores de terminal server (escritorios remotos),
que ofrecen la posibilidad a los usuarios de conectarse indistintamente al
que ellos quieran para poder trabajar con su escritorio y sus programas
definidos.

Hace un par de días, formateamos uno de los equipos, para hacerlo totalmente
nuevo, el problema que nos hemos encontrado es que cuando un cliente rdp,
diferente del 6.1 para XP y de un cliente Linux, intenta acceder al servidor,
le aparece este mensaje de error:

"Debido a un error de seguridad, el cliente no puede conectarse al servidor
Terminal Server"

Sin embargo este mismo cliente (estación de trabajo) se intenta conectar a
otro de los servidores que ya tenemos trabajando y funciona correctamente.
Los sistemas que tenemos instalados son Windows 2003 server SP2 standard
actualizado.

No sabemos que hacer. Ya que la mitad de los clientes que tenemos se
conectan por el cliente de rdp de windows version 5.2 y no los podemos
actualizar a la 6.1, porqué el sistema operativo que tienen instalado es
windows NT.

Se agradece cualquier sugerencia.
Muchas gracias.