Hi,
it seems a network issue. check if the DNS network flow port 53 used by the client to send DNS request is opened between client and new DNS server. you can use this tools https://www.microsoft.com/en-us/download/details.aspx?id=24009
It can be also a DC problem because the DNS zone is active directory integrated so , it can be impacted if there is a replication issue.
Please don't forget to mark this reply as answer if it help you to fix your issue