Did it work on the previous build you were using? I know that it's a huge pain to get a NT4 machine onto a 2k3+ domain. I've never tried using a newer machine to join a domain older than the client (except for XP clients to a 2k domain). Also, to get Vista to join a NT4 domain, you have to lower the security requirements. Another way around that I used in XP when it wouldn't play nice was to, instead of changing the PC's friendly name, I would go to the Network ID button and run thru the wizard. If it atleast finds the DC, then the wizard should work every time.
Quote from Joining NT Domain
"Under Local Policies > Security Options
Change the value of "Network Security: [COLOR=blue !important][COLOR=blue !important]LAN[/COLOR][/COLOR]
Manager authentication level"
from "NTVLM2 responses only" to "LM and NTLM - use NTLMv2 session security
Note that I last tried this with build 5384. Newer builds may need a