Qualquer servidor DNS para o qual seu Ubuntu esteja apontando (em /etc/resolv.conf) provavelmente ainda tem (ou teve) a entrada antiga em cache. Se se esquecer de abandonar o TTL pelo menos um período de tempo de TTL antes de fazer uma alteração, você se deparará com isso. Por exemplo, se sua entrada original tiver um TTL de 1 dia, isso significa que ela pode ser armazenada em cache por 1 dia e se você alterá-la logo após algum servidor remoto ter perguntado sobre ela, será 1 dia antes que o servidor retorne para obter o nova resposta.
É muito comum causar isso, porque você fez uma conexão ao site no antigo endereço antes de alterá-lo.
Verifique com o que seu TTL foi definido e esse será o período de tempo máximo (a partir do momento em que você o altera) até que ele seja realmente visível em todos os lugares.
E no futuro, planeje com antecedência para isso. É realmente difícil obter o cache de cada servidor DNS limpo pela Internet (há milhões).