Caso você ainda possa acessar a Internet, tente abrir o Centro de Software. Selecione Editar e fontes de software. De lá, certifique-se de que o "Download de" está definido como "Servidor Principal". Caso contrário, selecione-o e digite $ sudo apt-get update
no terminal. Resultado ainda é o mesmo?