Bug#679419: This bug still exists in stretch, by the way.

[Lukas Bürgi]

Just encountered it, system time was wrong, I ran apt-get update first
thing after booting and system time was automatically fixed while
apt-get was running.