Naming information cannot be located because:
The directory or file cannot be created.
Contact your system administrator to verify that your domain is properly configured and is currently online.
When performing a netdom query dc on the new domain controller it complained time is out.
Fixing up the time to ensure it is within 5 minutes of the PDC Emulator (as required for Kerberos) resolved the problem.
Easy one but had me stumped for a little while (I didn't glance at my system tray to check the clock until a while).