It could be a DNS problem rather than a vista one. If you are running 2003 server R2 (or really any version) and server is configured to be Domain Controller, DNS Server and Active Directory is setup If you delete the forward lookup zone only, reboot re-create forward lookupzone, reboot again then try and join client to the domain. If this does not work I would still consider it to be a DNS problem and keep digging into the event logs to find the problem.

Hope this works for you, it did for me...