Prueba reemplazando la dirección IP del DNS del servidor viejo al nuevo para verificar el cambio.
Por lo que comentas, parece un problema en red, debido que son todos los equipos con el problema, en una empresa que hice un trabajo, pasaba algo similiar y el problema era los DNS, debibo que el primer DNS trataba de resolver, al no poder, consultaba al 2do DNS y este le resolvia, pero el primero tardaba entre 1 a 2 minutos (si mal no recuerdo).
Te suguiero verifica bien la topologia de la red para verificar que no te este pansando algo similiar a como me paso.
Saludos desde Costa Rica