Ubuntu – Unable to locate ntpd package

NTP daemons don't want to do a sudden massive jump in system time. For one, it borks the chronology of entries in your log files, system daemons might freak out, etc. What it does instead is "drift" your system clock into place. If you want to check how far off from "the actual time" you are you can query an ntp server:

ntpdate -q pool.ntp.org

NTP works by adjusting the length of a second on your system by a slight bit so that you slowly get the correct time. It can take a while for the drift to happen if your offset is high. What you can do though is force a hard sync once:

service ntp stop
ntpdate pool.ntp.org
service ntp start

Edit: in response to the comments below.

Set this line up in /etc/default/ntpdate

NTPDATE_USE_NTP_CONF=yes

Your hosting provider is blocking ntp packets. This heavy handed approach has been implemented by some ISPs in response to the DDoS attacks. You can see that ntpdate is sending the packets fron the ntpdate -vd :

transmit(91.189.94.4)
transmit(91.189.89.199)
transmit(91.189.94.4)
transmit(91.189.89.199)

I would contact your ISP and ask if they are blocking external ntp requests and if they have a local server that you can use for time sync.

There are a couple more obscure possibilities but it is tough to rule them out since you have not posted any logs from syslog.