HOla
es extrano tu problema si estas usando XP profesional!!
a veces sucede que creando primero el pc dentro de users and computers en el server.... crea problemas de seguridad en relacion a los objetos.
Es decir lo mejor es unir el pc cliente sin haberlo creado antes en el dominio!!
Otra cosa importante es que si tu creaste un pc en el active directory que luego elimininas por algun motivo, pero luego creas otro pc con el mismo nombre a veces te dara error porque utilizas el mismo nombre aunque ya lo hayas eliminado.
otra cosa que puedes verificar aunque si dices que todo lo tienes bien, es ver que en el protocolo tcp/ip tengas habilitado el netbeui o netbios. (siempre esto en el cliente)
ciao