Comment 15 for bug 1678187

I've recreated this on Ubuntu 16.04 now, it seems that the missing bit was creating a sufficiently small enough amount of free space on my /boot partition.

While running 'sudo apt install' did finish the removal and I was able to continue using apt, I did notice that I had a leftover / abandoned initrd.img-4.4.0-31-generic.