Verifique se o clock do hardware com bateria está funcionando bem. Em um terminal, digite
sudo hwclock
Isso mostrará o relógio do hardware. O sistema usa esse relógio para definir o relógio real do sistema operacional no momento da inicialização. Se este relógio também pular, pode haver um problema com a bateria, ou o sistema operacional está salvando a data errada ao desligar. Se o relógio do hardware estiver correto, o sistema operacional atualizado não está lendo corretamente na inicialização.
Você pode tentar eliminar essa última possibilidade inicializando a partir de um pendrive, live-cd ou, se instalado, para o Windows e verificando a data:
- Defina a data correta no sistema operacional
- Desligue o sistema operacional
- Inicialize com outro sistema operacional
- Verifique a data lá
EDIT (depois de determinar o hwclock não funciona): Eu encontrei um casal em links interessantes:
1) Gentoo: link
Deactivate:
Device Drivers -> Real Time Clock
Activate:
Device Drivers -> Character Devices -> HPET High Precision Event Timer
Device Drivers -> Character Devices -> Enhanced Real Time Clock Support
2) Ubuntu: link
Interessante: parece que a timidez pode estar causando esse problema neste caso.
3) Ubuntu (sem solução publicada): link