Não tenho certeza do que está acontecendo, mas consegui remover os kernels não assinados comentando a linha:
linux-check-removal $version
nos arquivos
/var/lib/dpkg/info/linux-image-unsigned-4.16.5-041605-generic.prerm
e / ou
/var/lib/dpkg/info/linux-image-unsigned-4.16.4-041604-generic.prerm
e continuando com o procedimento de remoção padrão apt-get
( ukuu-gtk
também funciona bem).