Comment 3 for bug 236719

I suspect the problem is your drift, not your proxy/firewall/gateway.

NTP tries to not only fix your clock offset, but also your clock drift. It has limits, however, and if your drift is too bad it just gives up after a while. You might be lucky to find a message about it in /var/log/messages, but as you've pointed out it's not exactly user friendly.

Windows probably use SNTP (Simple-NTP (network time protocol)) which periodically sends a single packet, guesstimats the time offset and simply steps the clock if necessary. Usually this gives a much worse result than NTP, but for a badly drifting clock like yours this simple approach actually works better.

The ntpdate program (from the ntpdate package) can step your clock for you:

$ sudo ntpdate ntp.ubuntu.com

run this periodically (as a CRON job perhaps) and you should have a 'working' time sync:

$ sudo crontab -e

(an editor starts, add the line following line then save and exit):
17 * * * * ntpdate ntp.ubuntu.com

(check)

$ sudo crontab -l
# m h dom mon dow command
17 * * * * ntpdate ntp.ubuntu.com

Stepping the time like this is probably not doing much for the rest of your system, especially if you're stepping time backwards.
Various programs use things like file times to figure out what is going on, and having time leap around is likely to confuse them badly (e.g. "make" won't know what's out of date).
Stepping time forward can be just as bad, CRON jobs can get missed...