So I just installed a clients new AD DC Server and then tried to add a machine to the domain with no success. DNS SRV records were missing.

After searching I found this command to repair an re-add the DNS records to the server.

dcdiag /fix

I then reloaded the DNS Zone and restarted the DNS service.

All the DC records were added and the machine was added to the domain perfectly afterwards.

I hope this helps someone out there!