1311 0x51f ERROR_NO_LOGON_SERVERS

This might be a useless post for many of you, but it is something that I could have spent a lot of time looking into had I not come across it near knock-off time.

I recently decided to start moving our AD servers away from WS2012R2 and towards WS2016 Core. Before promoting my new domain controllers though, I also moved from FRS to DFS as I had received a warning stating that FRS had been deprecated. Doing this made me a little bit paranoid and so after I added my new DCs I went looking for problems. I found a few warnings about DNS and did the usual rebooting and what not, however, there was one warning that just wouldn't go away.

NETLOGON ErrorID 5781:
Dynamic registration or deletion of one or more DNS records associated with DNS domain 'ForestDnsZones.contoso.com.' failed. These records are used by other computers to locate this server as a domain controller (if the specified domain is an Active Directory domain) or as an LDAP server (if the specified domain is an application partition)...
USER ACTION
Fix possible misconfiguration(s) specified above and initiate registration or deletion of the DNS records by running 'nltest.exe /dsregdns' from the command prompt on the domain controller or by restarting Net Logon service on the domain controller.

Since I still had my other DCs running at this stage, this wasn't a huge issue and I wouldn't have even noticed it had I not gone looking. I ran the command from the warning and expected to see that all was well...it was not. I got an error message 1311 0x51f ERROR_NO_LOGON_SERVERS on both of my new AD servers. I looked into this for probably 45 minutes or so and then knocked off. The next morning I come in and run the test again and it's all good! The warning message has stopped appearing also. I gave the servers a reboot for good measure