Eu sei que isso pode parecer fora do padrão, mas você já tentou criar um novo arquivo sources.list com a página do Ubuntu Sources Generator? Pode fazer você um sources.list padrão do Ubuntu com apenas alguns cliques; depois salve-o, copie-o na sources.list original (apagando o que estava lá antes) e depois atualize. Pode até adicionar alguns PPAs comuns. Eu tive problemas com uma atualização dupla (13.04 a 13.10 a 14.04) e alguns dos PPAs estavam entrando em conflito com a lista atual, então eu criei um novo com apenas 14.04 coisas confiáveis para atualizar sem erros, e adicionarei os PPAs mais tarde (alguns ainda não tem fontes Trusty ainda).
Experimente ... se o seu APT estiver corrompido, o que você pode perder?