We just resolved this problem. While the remedies listed didn't work, it turned out the the mirror had an inconsistent set of resources. Specifically the anl ubuntu mirror has most items under http://mirror.anl.gov/pub/ubuntu/, the lucid-updates is under http://mirror.anl.gov/ubuntu/, even thought there was another, older lucid-updates in http://mirror.anl.gov/pub/ubuntu/
So, when all else fails, look really carefully at sources.list and at the mirror.
Bookmarks