I have encountered the same symptom. By doing ntpdate -d, I found the problem to be that it was trying to use an IPv6 address instead of the IPv4 address. This is a known problem http://bugs.debian.org/293793
that apparently has been resolved. Try ntpdate with the IP numbers, not the DNS name, of the server, and see if that works.
Liam
