I have the same problem after upgrading to the latest beta of Intrepid. Trying to update the time through the clock applet produces the error mentioned before. It remains so after a reboot.

Linux walterheck-laptop 2.6.27-7-generic #1 SMP Tue Oct 14 18:40:44 UTC 2008 i686 GNU/Linux

my syslog says:
walterheck@walterheck-laptop:~$ grep ntpd /var/log/syslog     
Oct 17 07:46:16 walterheck-laptop ntpd[5518]: ntpd exiting on signal 15
Oct 17 07:46:17 walterheck-laptop ntpdate[7809]: can't find host clock.tricity.wsu.edu 
Oct 17 10:55:04 walterheck-laptop ntpdate[7809]: step time server 193.67.79.202 offset 11326.571568 sec
Oct 17 10:55:04 walterheck-laptop ntpd[7849]: ntpd 4.2.4p4@1.1520-o Wed Aug 20 17:03:52 UTC 2008 (1)
Oct 17 10:55:04 walterheck-laptop ntpd[7850]: precision = 2.000 usec
Oct 17 10:55:04 walterheck-laptop ntpd[7850]: Listening on interface #0 wildcard, 0.0.0.0#123 Disabled
Oct 17 10:55:04 walterheck-laptop ntpd[7850]: Listening on interface #1 lo, 127.0.0.1#123 Enabled
Oct 17 10:55:04 walterheck-laptop ntpd[7850]: Listening on interface #2 wlan0, 192.168.1.101#123 Enabled
Oct 17 10:55:04 walterheck-laptop ntpd[7850]: kernel time sync status 0040
Oct 17 10:55:04 walterheck-laptop ntpd[7850]: frequency initialized -49.214 PPM from /var/lib/ntp/ntp.drift
Oct 17 10:55:04 walterheck-laptop ntpd[7850]: getaddrinfo: "::1" invalid host address, ignored
Oct 17 10:55:07 walterheck-laptop ntpd_initres[7853]: couldn't resolve `clock.tricity.wsu.edu', giving up on it
Oct 17 10:58:18 walterheck-laptop ntpd[7850]: synchronized to 213.222.193.35, stratum 1
Oct 17 10:58:18 walterheck-laptop ntpd[7850]: kernel time sync status change 0001
Oct 17 11:19:50 walterheck-laptop ntpd[7850]: synchronized to 193.67.79.202, stratum 1
Oct 17 12:22:20 walterheck-laptop ntpd[7850]: synchronized to 213.222.193.35, stratum 1
Oct 17 12:31:41 walterheck-laptop ntpd[7850]: synchronized to 193.67.79.202, stratum 1
Oct 17 14:23:39 walterheck-laptop ntpd[7850]: synchronized to 213.222.193.35, stratum 1
Oct 17 14:32:18 walterheck-laptop ntpd[7850]: synchronized to 193.67.79.202, stratum 1
Oct 17 15:59:25 walterheck-laptop ntpd[7850]: synchronized to 213.222.193.35, stratum 1
Oct 17 16:06:01 walterheck-laptop ntpd[7850]: synchronized to 193.67.79.202, stratum 1
Oct 17 17:28:17 walterheck-laptop ntpd[7850]: synchronized to 213.222.193.35, stratum 1
Oct 17 17:32:03 walterheck-laptop ntpd[7850]: synchronized to 193.67.79.202, stratum 1
Oct 17 07:46:06 walterheck-laptop ntpd[5517]: ntpd 4.2.4p4@1.1520-o Wed Aug 20 17:03:52 UTC 2008 (1)
Oct 17 07:46:06 walterheck-laptop ntpd[5518]: precision = 2.000 usec
Oct 17 07:46:06 walterheck-laptop ntpd[5518]: Listening on interface #0 wildcard, 0.0.0.0#123 Disabled
Oct 17 07:46:06 walterheck-laptop ntpd[5518]: Listening on interface #1 lo, 127.0.0.1#123 Enabled
Oct 17 07:46:06 walterheck-laptop ntpd[5518]: kernel time sync status 0040
Oct 17 07:46:06 walterheck-laptop ntpd[5518]: frequency initialized -2.440 PPM from /var/lib/ntp/ntp.drift
Oct 17 07:46:06 walterheck-laptop ntpd[5518]: getaddrinfo: "::1" invalid host address, ignored
Oct 17 07:46:08 walterheck-laptop ntpd_initres[5533]: couldn't resolve `ntp.ubuntu.com', giving up on it
Oct 17 07:46:08 walterheck-laptop ntpd_initres[5533]: couldn't resolve `clock.tricity.wsu.edu', giving up on it
Oct 17 07:46:08 walterheck-laptop ntpd_initres[5533]: couldn't resolve `ntp0.nl.net', giving up on it
Oct 17 07:46:08 walterheck-laptop ntpd_initres[5533]: couldn't resolve `ntp.certum.pl', giving up on it
Oct 17 07:47:25 walterheck-laptop ntpd[5518]: ntpd exiting on signal 15
Oct 17 07:47:25 walterheck-laptop ntpdate[6783]: can't find host clock.tricity.wsu.edu 
Oct 17 17:51:00 walterheck-laptop ntpdate[6783]: step time server 193.67.79.202 offset 36214.808066 sec
Oct 17 17:51:01 walterheck-laptop ntpd[6822]: ntpd 4.2.4p4@1.1520-o Wed Aug 20 17:03:52 UTC 2008 (1)
Oct 17 17:51:01 walterheck-laptop ntpd[6823]: precision = 2.000 usec
Oct 17 17:51:01 walterheck-laptop ntpd[6823]: Listening on interface #0 wildcard, 0.0.0.0#123 Disabled
Oct 17 17:51:01 walterheck-laptop ntpd[6823]: Listening on interface #1 lo, 127.0.0.1#123 Enabled
Oct 17 17:51:01 walterheck-laptop ntpd[6823]: Listening on interface #2 wlan0, 192.168.1.101#123 Enabled
Oct 17 17:51:01 walterheck-laptop ntpd[6823]: kernel time sync status 0040
Oct 17 17:51:01 walterheck-laptop ntpd[6823]: frequency initialized -2.440 PPM from /var/lib/ntp/ntp.drift
Oct 17 17:51:01 walterheck-laptop ntpd[6823]: getaddrinfo: "::1" invalid host address, ignored
Oct 17 17:51:03 walterheck-laptop ntpd_initres[6828]: couldn't resolve `clock.tricity.wsu.edu', giving up on it
Oct 17 17:54:12 walterheck-laptop ntpd[6823]: synchronized to 91.189.94.4, stratum 2
Oct 17 17:54:12 walterheck-laptop ntpd[6823]: kernel time sync status change 0001
Oct 17 18:00:41 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 17 20:30:18 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 17 20:38:30 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 17 20:54:55 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 17 20:59:26 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 17 21:07:50 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 17 21:14:27 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 17 21:24:10 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 17 21:29:04 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 17 21:34:32 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 17 21:43:08 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 17 22:12:33 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 17 22:21:48 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 17 23:35:50 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 17 23:43:16 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 18 00:36:50 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 18 00:50:34 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 18 01:36:46 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 18 03:01:04 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 18 03:01:40 walterheck-laptop ntpd[6823]: time reset -0.165504 s
Oct 18 03:06:28 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 18 03:33:20 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 18 03:36:41 walterheck-laptop ntpd[6823]: time reset +0.168079 s
Oct 18 03:42:19 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 18 03:54:10 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 18 04:03:45 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 18 04:24:17 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 18 04:35:44 walterheck-laptop ntpd[6823]: synchronized to 193.67.79.202, stratum 1
Oct 18 04:45:43 walterheck-laptop ntpd[6823]: synchronized to 213.222.193.35, stratum 1
Oct 17 07:42:28 walterheck-laptop ntpd[5497]: ntpd 4.2.4p4@1.1520-o Wed Aug 20 17:03:52 UTC 2008 (1)
Oct 17 07:42:28 walterheck-laptop ntpd[5498]: precision = 2.000 usec
Oct 17 07:42:28 walterheck-laptop ntpd[5498]: Listening on interface #0 wildcard, 0.0.0.0#123 Disabled
Oct 17 07:42:28 walterheck-laptop ntpd[5498]: Listening on interface #1 lo, 127.0.0.1#123 Enabled
Oct 17 07:42:28 walterheck-laptop ntpd[5498]: kernel time sync status 0040
Oct 17 07:42:28 walterheck-laptop ntpd[5498]: frequency initialized 8.993 PPM from /var/lib/ntp/ntp.drift
Oct 17 07:42:28 walterheck-laptop ntpd[5498]: getaddrinfo: "::1" invalid host address, ignored
Oct 17 07:42:30 walterheck-laptop ntpd_initres[5515]: couldn't resolve `ntp.ubuntu.com', giving up on it
Oct 17 07:42:30 walterheck-laptop ntpd_initres[5515]: couldn't resolve `clock.tricity.wsu.edu', giving up on it
Oct 17 07:42:30 walterheck-laptop ntpd_initres[5515]: couldn't resolve `ntp0.nl.net', giving up on it
Oct 17 07:42:30 walterheck-laptop ntpd_initres[5515]: couldn't resolve `ntp.certum.pl', giving up on it
Oct 17 10:52:29 walterheck-laptop ntpd[5498]: Listening on interface #2 wlan0, 192.168.1.101#123 Enabled

I should probably also mention that i accidentally issued a "chown walterheck /" (don't laugh, it was late ;) ) last night, but I seem to remember my clock being wrong ever since the upgrade from Hardy two or three nights ago.

Hope this helps...