Ok, para referência futura, aqui está a solução final (com alguma ajuda das outras respostas).
O problema era que o clock do hardware estava errado, e que aparentemente devido a problemas de firewall, o clock do ubuntu não pode ser atualizado automaticamente. A hora do relógio do hardware pode ser alterada, seja manualmente, fazendo
sudo hwclock --set --date="02/07/2015 10:21:00"
por exemplo (com data na hora local), ou conectando-se ao tempo mantendo os servidores online (o que não funcionou para mim por causa dos problemas de firewall)
sudo ntpdate -u time.nist.gov
Em seguida, a hora do sistema do kernel do Ubuntu ainda tem que ser atualizada para este novo tempo, caso contrário, o tempo mostrado ainda estará errado e, mais importante, o Ubuntu irá substituir o novo tempo de hardware novamente. Isso é feito facilmente com
sudo hwclock -s