Primeiramente, verifique se o seu servidor de nomes realmente funciona corretamente. Sob o Linux use
dig @ your.name.server www.example.com
e verifique se ele faz o que você deseja. No Windows, use o nslookup e, quando estiver no prompt (inicie-o no modo interativo), altere o servidor de nomes para o seu servidor de nomes e, em seguida, insira www. example.com e verifique os resultados.
Se estes testes voltarem bem, então é simplesmente uma questão de esperar (como apontado por outras respostas, no futuro é uma boa idéia manter seu TTL curto se você estiver planejando fazer mudanças).