My machine was off by two hours after a restart even though
/etc/timezone pointed to the correct timezone.
A temporary solution was to execute the following command in bash:
sudo date -s "$(wget -qSO- --max-redirect=0 google.com 2>&1 | grep Date: | cut -d' ' -f5-8)Z"
I solved it by installing
htpdate and setting my time this way. If you are interacting with a Windows Domain are doing other authentication based on time you are way better off using the network time protocol, unfortunately this is not available in my case.