mudança de DNS envolve uma certa dose de magia negra
quando você sabe de antemão que vai mudar um IP ou algo assim, ideal é ir baixando o TTL (time to live, o prazo de validade do cache) do mapa todo ou das entradas que vão mudar pra períodos mais curtos à medida em que o dia e a hora da mudança se aproxima, de modo que não sobre cache antigo espalhado por aí uma vez que se faça a mudança
duro é quando a mudança é de surpresa. se o TTL tava configurado pra 1 semana, o cache com informação obsoleta pode durar isso tudo
mas, mesmo com todos esses cuidados, quando dá problema, é sempre o DNS ;-)