We were seeing:

Your computer could not be joined to the domain. You have exceeded the maximum number of computer accounts you are allowed to create in this domain. Contact your system administrator to have this limit reset or increased.

It turns out that a standard user can only add 10 machines to a domain, so make sure you are using a domain admin account instead...