O primeiro passo é cortar as ferramentas "intermediárias" e trabalhar com comandos que são invocados em seu nome:
sudo apt-get check && sudo apt-get update
# you may need to repeat the update if it complains
sudo apt-get upgrade
Quaisquer erros gerados por esses comandos seriam mais informativos quando anexados à sua pergunta original. Se o check
falhar, faça como instrui ou pare e poste seu resultado.