Apt fails to remove partially installed kernel and can't install any other packages

Apt is failing to upgrade or install new packages after a seeming partial kernel upgrade. I've tried apt-get purge -f linux-image-extra-3.19.0-22-generic which fails with a very similar error message. The machine also crashes on boot into the newest kernel version (default in grub), but previous versions work fine.

$ sudo apt-get upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
Calculating upgrade... Done
The following packages will be REMOVED:
  linux-image-3.19.0-22-generic linux-image-extra-3.19.0-22-generic
The following packages will be upgraded:
  linux-cloud-tools-common
1 upgraded, 0 newly installed, 2 to remove and 0 not upgraded.
2 not fully installed or removed.
Need to get 0 B/24.3 kB of archives.
After this operation, 208 MB disk space will be freed.
Do you want to continue? [Y/n] y
(Reading database ... 453815 files and directories currently installed.)
Removing linux-image-extra-3.19.0-22-generic (3.19.0-22.22) ...
depmod: FATAL: could not load /boot/System.map-3.19.0-22-generic: No such file or directory
run-parts: executing /etc/kernel/postinst.d/apt-auto-removal 3.19.0-22-generic /boot/vmlinuz-3.19.0-22-generic
run-parts: executing /etc/kernel/postinst.d/dkms 3.19.0-22-generic /boot/vmlinuz-3.19.0-22-generic
run-parts: executing /etc/kernel/postinst.d/initramfs-tools 3.19.0-22-generic /boot/vmlinuz-3.19.0-22-generic
update-initramfs: Generating /boot/initrd.img-3.19.0-22-generic
grep: /boot/config-3.19.0-22-generic: No such file or directory
depmod: WARNING: could not open /tmp/mkinitramfs_6gldfB/lib/modules/3.19.0-22-generic/modules.order: No such file or directory
depmod: WARNING: could not open /tmp/mkinitramfs_6gldfB/lib/modules/3.19.0-22-generic/modules.builtin: No such file or directory
run-parts: executing /etc/kernel/postinst.d/pm-utils 3.19.0-22-generic /boot/vmlinuz-3.19.0-22-generic
run-parts: executing /etc/kernel/postinst.d/unattended-upgrades 3.19.0-22-generic /boot/vmlinuz-3.19.0-22-generic
run-parts: executing /etc/kernel/postinst.d/update-notifier 3.19.0-22-generic /boot/vmlinuz-3.19.0-22-generic
run-parts: executing /etc/kernel/postinst.d/zz-update-grub 3.19.0-22-generic /boot/vmlinuz-3.19.0-22-generic
Generating grub configuration file ...
ERROR: cannot determine partition label for rootfs /dev/sda9
run-parts: /etc/kernel/postinst.d/zz-update-grub exited with return code 1
dpkg: error processing package linux-image-extra-3.19.0-22-generic (--remove):
 subprocess installed post-removal script returned error exit status 1
Removing linux-image-3.19.0-22-generic (3.19.0-22.22) ...
Examining /etc/kernel/postrm.d .
run-parts: executing /etc/kernel/postrm.d/initramfs-tools 3.19.0-22-generic /boot/vmlinuz-3.19.0-22-generic
update-initramfs: Deleting /boot/initrd.img-3.19.0-22-generic
run-parts: executing /etc/kernel/postrm.d/zz-update-grub 3.19.0-22-generic /boot/vmlinuz-3.19.0-22-generic
Generating grub configuration file ...
ERROR: cannot determine partition label for rootfs /dev/sda9
run-parts: /etc/kernel/postrm.d/zz-update-grub exited with return code 1
Failed to process /etc/kernel/postrm.d at /var/lib/dpkg/info/linux-image-3.19.0-22-generic.postrm line 328.
dpkg: error processing package linux-image-3.19.0-22-generic (--remove):
 subprocess installed post-removal script returned error exit status 1
Errors were encountered while processing:
 linux-image-extra-3.19.0-22-generic
 linux-image-3.19.0-22-generic
E: Sub-process /usr/bin/dpkg returned an error code (1)

I need to get apt working again and into a state where it can install future kernels. Properly purging the 3.19.0-22 kernel would be nice but unnecessary. Feel free to ask for more information, and thanks in advance

--Edits--

0x450's answer works for any non-kernel related packages. Kernel and grub updates return apt and dpkg to a broken state. I have noticed this recurring error message:

Generating grub configuration file ... ERROR: cannot determine partition label for rootfs /dev/sda9

Could this be an issue related to grub configuration files?

sudo apt-get install --reinstall linux-image-extra-3.19.0-22-generic results in a very similar error (which can be viewed here)

sudo dpkg --configure -a creates this error

sudo apt-get purge linux-image-extra-3.19.0-22-generic creates this error

I struggled with the exact same problem but the broken kernel packages were version 3.13.0.57.

Inspect the problem:

Check the dpkg status of the packages:

dpkg --status linux-image-3.19.0-22-generic
dpkg --status linux-image-extra-3.19.0-22-generic

If the output states that the packages are in bad state, i.e. half installed or not fully installed, this means that they have broken apt-get and dpkg respectively.

The solution:

The entries of the infected kernel packages must be deleted manually from the status file of dpkg in order apt-get and dpkg itself to function normally once again. The steps are as follows:

1. Make sure to create a back up of the status file just in case if something goes wrong.

   sudo cp /var/lib/dpkg/status /var/lib/dpkg/status.backup

2. Open /var/lib/dpkg/status with your preferred text editor and search and delete ONLY the references of the broken packages. You must not delete anything else!

3. Run sudo apt-get update and sudo apt-get upgrade to make sure that everything is fixed.

4. This step is optional since the packages are no longer tracked from the package managers but if you want you can free some disk space by deleting them. You can safely remove manually all of the entries of the broken kernel packages in /boot and in /usr/src but be VERY CAREFUL. Make sure to touch only the files/folders, which correspond to the 3.19.0-22 version in your case.

Root cause

The root problem seems to be that /boot/System.map-3.19.0-22-generic is missing, which prevents reconfiguration/removal of the packet.

Suggested Solutions

My initial suggestion was sudo apt-get install --reinstall linux-image-extra-3.19.0-22-generic

As this apparently fails ("cannot configure half-installed"), I would suggest to do this a bit more forceful, e.g. with the following options

sudo dpkg --remove --force-remove-reinstreq linux-image-extra-3.19.0-22-generic

That suggestion is based on this answer.

Alternative: Manual repair?

Alternatively, you can also try to manually repair that file? Maybe it is unpacked by apt-get while trying to reinstall? It's a bit hard for me to replicate on my system right now