This is a follow up issue after recreating my domain from this thread.
I was able to add all computers back into the domain by changing them to a workgroup, rebooting, changing back to the domain, rebooting...
except for two computers. Oddly enough both are laptops that connect to the network wirelessly.
On both when I try to rejoin the domain I get the error "server cannot perform the requested operation".
When I check the server I see the computer is listed in active directory computers, however it is disabled.
Both laptops are using the correct dns (and it worked for every computer other than the two laptops).
I have also tried running mmc and adding the "Security Configuration and Analysis" and "Security Templates" snap-ins, created a new database and imported the security setup template, applied the templated, rebooted and retried to join the domain and got the same error.
I can ping the dnc, and the dns is functioning properly (I can browse sites by both name and IP).
I'm running out of ideas and any help is greatly appreciated.