Você pode ter sido mordido por um caso extremo de ntpd:
Versões ntpd do IIRC < 4.2.4p3 removeu todos os servidores da sua lista de sincronização que não puderam ser alcançados em algum momento. Isso é obviamente muito ruim nesse caso, já que o ntpd pode muito bem 'esgotar' a lista de seus pares antes de ganhar conectividade com a Internet.
Poderíamos / podemos definir a opção dynamic
para esses servidores em ntp.conf
para contornar esse problema.
Com versões mais novas, isso não deve ser mais necessário (também, a opção dinâmica foi desativada em algum momento, o que causou pequenas queixas para algumas pessoas com queixas de ntp, de repente).
Assim, você pode atualizar seu ntpd ou definir a opção.
Como uma terceira opção, você pode criar uma dependência adequada em seu sistema init; fazendo o ntpd depender de uma conexão internet estabelecida ( não apenas rede). O resultado seria que você pode reutilizar isso com outros serviços também.