I am having the same problem except my machines are fresh installs of Windows XP SP2 in an AD domain. Firewall service is completely disabled (otherwise you wouldn't get the message about not running windows nt, instead you would get cannot find computer) and I've checked DNS which is 100% functional. I've also tried unjoining/rejoining computers to the domain with no success. This started happening earlier this year out of nowhere, and every new machine I add to the domain exhibits this problem. I am unable to find any information about this anywhere. What else is there to check on a fresh install?
