Solution 1:

Turn ntpd back on. It's job is to figure out how fast the clock is running and apply an appropriate correction.

Solution 2:

Virtual servers have notoriously unreliable clocks, since they don't get reliable ticks from the CPU. They're even worse than the clocks in physical machines. It depends mostly on the load of the hypervisor your VPS is running on, so maybe you're seeing more drift since the load of the physical server has increased.

Simply enable NTPD, and point it to some NTP servers. NTP will figure out how fast your clock drifts, and will slow it down by the right amount. It will periodically monitor and adjust these values, leading to very accurate time. The NTPD daemon takes few resources and is very effective, so I would suggest just enabling it.

Solution 3:

The ntpdate command is a one-off. You want the ntpd daemon running to make minute adjustments.

# /etc/init.d/ntpd stop
# ntpdate time.nist.gov
# /etc/inid.d/ntpd start
# watch 'ntpq -pn'

Pay attention to the symbols on the left hand side of the output of ntpq. Those will tell you once you have a sync.