Ubuntu's clock is off by about a half hour:

Where do I even start troubleshooting this?

It's allegedly being set "automatically from the Internet". How can I verify that "the Internet" knows what time it is?

Details

Ubuntu has had plenty of time to communicate with the Internet:

$ date; uptime
Fri May 18 05:56:00 PDT 2012
 05:56:00 up 12 days, 10:48,  2 users,  load average: 0.61, 0.96, 1.15

This time server I found via a web search does appear to know the correct time:

$ date; ntpdate -q north-america.pool.ntp.org
Fri May 18 05:56:09 PDT 2012
server 208.38.65.37, stratum 2, offset 1752.625337, delay 0.10558
server 46.166.138.172, stratum 2, offset 1752.648597, delay 0.10629
server 205.189.158.228, stratum 3, offset 1752.672466, delay 0.11829
18 May 05:56:18 ntpdate[29752]: step time server 208.38.65.37 offset 1752.625337 sec

There aren't any reported errors related to NTP:

$ grep -ic ntp /var/log/syslog
0

After rebooting, the time was automatically corrected and the following appeared in /var/log/syslog:

May 18 17:58:12 aux ntpdate[1891]: step time server 91.189.94.4 offset 1838.497277 sec

A log of the offset reported by ntpdate reveals that the clock is drifting by about 9 seconds every hour:

$ while true; do ntpdate-debian -q | tail -n 1 >> 'drift.log'; sleep 16m; done
^C
$ r -e '
    attach(read.table("drift.log", header=FALSE))
    clock <- as.POSIXct(paste(V1, V2, V3), format="%d %b %H:%M:%S")
    fit <- lm(V10~clock)
    png("drift.png")
    plot(clock, V10, xlab="Clock time", ylab="Time server offset (s)")
    abline(fit)
    mtext(sprintf("Drift rate: %.2f s/hr", fit$coefficients[[2]]*3600))
'