Eu tive o mesmo problema, iv tentei em vez de sudo apt-get update eu digitei no gksudo apt-get update, ele irá pedir ur senha, vai buscar e baixar coisas, no final eu consegui:
E: Some index files failed to download. They have been ignored, or old ones used instead.
Então eu corri novamente o software de atualização que funcionou (eu tenho o código do código nas configurações marcadas)
não me pergunte como ou porque tem sido 1 mês desde que eu tenho usado o Ubuntu: P acabou de ter sorte!