Tive o mesmo problema
após algumas pesquisas, descobri que a atualização foi feita apenas parcialmente. Aparentemente, alguns programas adicionam linhas em branco na descrição do pacote, quebrando a ferramenta apt-get. (No meu caso foi bricscad, eu li coisas parecidas sobre drivers lexmark)
use
sudo apt-get -f instalar
se der uma mensagem de erro reclamando de linhas em branco nos arquivos, edite esses arquivos (exclua as linhas em branco) depois você pode correr
sudo apt-get upgrade
para concluir a atualização