Was getting this error when trying to do a partial upgrade in Ubuntu (I didn’t select ‘Partial Upgrade’, it brought it up on its own). Then checked in Synaptic->Repositories->Authentication. Apparently, http://ppa.launchpad.net jaunty was not authenticated.
A quick google brought me to this post. Looks like I’m not the only one with this problem. I followed the instructions left by one of the users and that fixed the authentication problem.
Then tried running the Partial upgrade again and it worked!