This sounds like the same thing that happened to us on debian squeeze. Check out this post.
To fix, on the ubuntu server having issues, try these commands:
(date +"%H:%M:%S" |perl -pe 'chomp';echo `date +"%N"` / 999999999|bc -l) | sudo perl -ne 'chomp;system ("date","-s",$_);'
If you don't have perl installed for some reason, you can replace the middle date command with a simpler one referenced in the post above.