I've also followed the tip to run the following command:
sudo dpkg --remove --force-remove-reinstreq <image-to-remove>.
However, my packages was so "corrupted" that when I ran this command I was followed by a list of dependencies that refused to remove the package. And with that upgrading the system was also a failure.
Finally I found out that I could edit /var/lib/dpkg/status and change the row of the damaged package:
Status: deinstall reinstreq half-installed
To
Status: install ok installed
With this changed, rerunning apt-get remove was suddenly successful.
A footnote of this is that in my case, it was linux-headers that needed to be reinstalled and linux-image-extra that was a dependency.
Also, after manipulating the file I've got a few warnings:
dpkg-query: warning: parsing file '/var/lib/dpkg/status' near line 1950 package 'linux-headers-4.4.0-65-generic':
missing description
dpkg-query: warning: parsing file '/var/lib/dpkg/updates/0066' near line 7 package 'linux-headers-4.4.0-65-generic':
missing description
They however disappeared right after running apt-get autoremove/upgrade, so I suspect that this is not the best way of removing packages that is impossible to remove.
sudo apt install linux-image-4.4.0-65-generic
? The "no archive" would DS like it means it's just not in your cache.