Broken DNS?

Run DCDiag /test:dns to test and see what errors it shows.

Even after clearing out DNS some entries might not be showing there but still be in AD so run ADSI Edit and look through the System section for errors. Mine was old DC entries appearing in MicrosoftDNS section.