Tente atualizar através de 'Terminal'. Abra o Dash, abra 'Terminal' e digite:
sudo apt-get update
Clique em Enter, digite sua senha do sistema e espere que ela termine. Isso pode resolver seu problema. Quando a atualização estiver concluída, tente novamente o gerenciador de atualização gráfica para ver se ele foi corrigido.
Se isso falhar, talvez seja necessário reparar o banco de dados do dpkg, você pode fazer isso com o seguinte comando no 'Terminal':
sudo dpkg --configure -a