Make sure that the workstation is setup to use the domain controller as the DNS server. You also need to make sure that the domain controller uses it self, and only it self as the domain controller.
You could also runs a few simple checks to make sure your communicating properly.
1. can you ping the server?
2. Is the firewall on the client preventing traffic?
3. Are you on the same subnet?
Simple things I know, but often stuff we overlook.
Try creating the workstation in the domain first and then add it. In other words, go into Active Directory Users & Computers and add the computer and then go through the computer identity wizard.