Another common problem preventing joining AD would be if the Mac clock is significantly out of sync with the AD controller. You can use your AD controller as a network time server to prevent this in future.
I recently setup a Mac image deployment system and was finding that the returned Macs often had been left on and as result had a flat battery which in turn reset the clock. So I had to add a step to first resync the clock before joining AD.
that was a good idea, but alas no. I was using the DC for the NTP so the clocks were in sync.
but have not restarted yet so I'll let you know.
but I did find that i was able to see the LDAP on my DC but not able to use AD to join...