Hola, ha funcionat.

He fet
sudo dpkg --force-all -P linux-image-4.4.0-101-generic
sudo dpkg --force-all -P linux-headers-4.4.0-101-generic

per als paquets antics.

He fet update i upgrade i em seguia dient lo de Proveu-ho emprant -f.

He fet sudo apt-get -f install i em seguia donant errors per la manca d'espai, és com si no ho hagués eliminat tot.
Llavors he vist que ja em deixava fer sudo apt remove linux-image-4.4.0-101-generic linux-headers-4.4.0-101-generic. I ho he fet per a tots els nuclis antics excepte els dos últims que ara són el 128 i el 130.
En els primers em donava errors però als darrers ja no, i m'anava recordant que m'havien quedat coses dels primer i que fes autoremove.
He fet autoremove, i sembla que ha tret coses sueltes que havien quedat.
Llavors he fet update i upgrade i ho ha fet sense cap problema.
Ja no em surt el missatge d'error. M'imagino que ja està tot bé.
Moltes gràcies wgarcia, és una passada la feina que fas, moltíssimes gràcies, de veritat.