The computer account doesnt need to in AD first.
As long as the account used to join to the domain has sufficient permissions it will creat the account and put in the computers O.U by default.
It does sound like it may be DNS related.
Check on your DNS server (probably best to use your AD Primary Domain controller) and make sure the P.C.s and servers are registered in the forward lookup zones with the correct IP addresses.
Have you managed to join ANYTHING to domain (other servers etc)
Also try and browse to your domain controllers network shares (sysvol or netlogon)
\\YourDCname\