My problem

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.