I got this error when joining a windows XP to the domain. I ensured that DNS resolution was working fine. After some testing I determined that the issue was NetBIOS resolution.
An Ipconfig /all showed that there was no WINS server address (even though DHCP should be giving one out) and NetBIOS over TCP was showing as disabled. I manually enabled this and added a WINS server address but another Ipconfig /all showed no change. Ok so the TCP/IP stack got corrupted, no biggie, easy to fix by removing the NIC drivers and re-adding them forcing Windows to create another stack but this leads into the rant.
Why do I need NetBIOS resolution to join an XP machine to the domain when I have DNS resolution? Why do I need NetBIOS resolution at all? NetBIOS resolution was crap 10 years ago and it’s even crappier and less necessary now. NetBIOS resolution is the tonsils of the network world. The worst part is that when NetBIOS resolution breaks you don’t even get a week off of school and all the ice cream you can eat.