Acabei de ter este problema com um site para o qual alterei o DNS e pesquisei uma solução para essa página.
Na minha experiência, o Firefox às vezes mantém seu próprio cache de DNS e não o limpa a tempo. Portanto, se você estiver visualizando um site no Firefox e continuar vendo o site antigo, tentar o Chrome pode resolver o problema. Se isso funcionar, você pode limpar o cache no Firefox. Isso aconteceu no Ubuntu, eu não sei se isso acontece no Windows ou OSX também.
Eu não tenho o nscd instalado. Notei no entanto que no terminal o novo DNS é encontrado vários minutos depois, então o problema se resolveu.