Tente isso, espero que funcione:
-
Faça um backup de
/var/lib/dpkg/status:sudo cp /var/lib/dpkg/status /var/lib/dpkg/status.bkup -
Abra
/var/lib/dpkg/status:sudo nano /var/lib/dpkg/status -
Pesquise no arquivo por qualquer referência ao nome desse pacote (por exemplo,
linux-headers-3.0.0-19) e CUIDADOSAMENTE exclua essa entrada. Não apague mais nada. Salve o arquivo e saia. -
Faça
sudo apt-get update.
Isso provavelmente deve resolver o problema.