Just to add the experience history here:
The same thing happened to me yesterday.
I tried to join a w2012 srv that was previously joined to a NS 6.8 DC but now the join did not work.
The NS 7 was configured as DNS server AD and Gateway, and I've added DNS records for all the hosts for the AD and NS itself...
Also in windows networking I've added the ip of NS as primary DNS server and the suffixes.
Still, the errors were different depending on what user i tried to join the domain with.
One of the errors was: the network path was not found or has been lost
Another was: that the domain does not exist or it could not be contacted.
nslookup resolved both the NS and AD from FQDN and both replied to ping on host.
So I somehow do not think that it was a DNS error.
When I'll have some time I'll try again to test.
Also a win 10 machine failed to join the domain but I given up on that more quickly.