Can't exactly help, but I do have the same problem - with Hardy (Gutsy was
always ok). Sometimes update works, but more often not. Synaptic likewise
sometimes solves it, but sometimes doesn't, and apt-get from terminal
always (so far) works.

(My machine is hard-wired to a wireless router and that to the broadband
router).