Pode ser que isso demore muito tempo e não seja interrompido. Eu estava tendo um problema semelhante e, finalmente, depois de deixá-lo por um longo tempo, percebi que está demorando muito para terminar e dar sem saída. Isso dá a aparência de ter sido interrompido porque normalmente o Linux e o apt são ao mesmo tempo verbosos e demoram aproximadamente o mesmo tempo para fazer as coisas.
EDIT: após investigação adicional, acredito que isso ocorra porque apt autoremove é (infelizmente para nós) inteligente o suficiente para executar update-grub cada vez que modifica um kernel, mesmo que seja um redundante. Eu percebi isso executando sudo update-grub manualmente depois, e com certeza, o mesmo grande período de espera.
Por exemplo, aqui está uma saída do meu autoremove:
Removing linux-image-extra-4.8.0-36-generic (4.8.0-36.36~16.04.1) ...
run-parts: executing /etc/kernel/postinst.d/apt-auto-removal 4.8.0-36-generic /boot/vmlinuz-4.8.0-36-generic
run-parts: executing /etc/kernel/postinst.d/initramfs-tools 4.8.0-36-generic /boot/vmlinuz-4.8.0-36-generic
update-initramfs: Generating /boot/initrd.img-4.8.0-36-generic
run-parts: executing /etc/kernel/postinst.d/pm-utils 4.8.0-36-generic /boot/vmlinuz-4.8.0-36-generic
run-parts: executing /etc/kernel/postinst.d/unattended-upgrades 4.8.0-36-generic /boot/vmlinuz-4.8.0-36-generic
run-parts: executing /etc/kernel/postinst.d/update-notifier 4.8.0-36-generic /boot/vmlinuz-4.8.0-36-generic
run-parts: executing /etc/kernel/postinst.d/zz-update-grub 4.8.0-36-generic /boot/vmlinuz-4.8.0-36-generic
Generating grub configuration file ...
Warning: Setting GRUB_TIMEOUT to a non-zero value when GRUB_HIDDEN_TIMEOUT is set is no longer supported.
Found linux image: /boot/vmlinuz-4.8.0-52-generic
Found initrd image: /boot/initrd.img-4.8.0-52-generic
Found linux image: /boot/vmlinuz-4.8.0-46-generic
Found initrd image: /boot/initrd.img-4.8.0-46-generic
Found linux image: /boot/vmlinuz-4.8.0-45-generic
Found initrd image: /boot/initrd.img-4.8.0-45-generic
Found linux image: /boot/vmlinuz-4.8.0-36-generic
Found initrd image: /boot/initrd.img-4.8.0-36-generic
Found linux image: /boot/vmlinuz-4.4.0-78-generic
Found initrd image: /boot/initrd.img-4.4.0-78-generic
Found memtest86+ image: /boot/memtest86+.elf
Found memtest86+ image: /boot/memtest86+.bin
done
Removing linux-image-4.8.0-36-generic (4.8.0-36.36~16.04.1) ...
Examining /etc/kernel/postrm.d .
run-parts: executing /etc/kernel/postrm.d/initramfs-tools 4.8.0-36-generic /boot/vmlinuz-4.8.0-36-generic
update-initramfs: Deleting /boot/initrd.img-4.8.0-36-generic
run-parts: executing /etc/kernel/postrm.d/zz-update-grub 4.8.0-36-generic /boot/vmlinuz-4.8.0-36-generic
Generating grub configuration file ...
Warning: Setting GRUB_TIMEOUT to a non-zero value when GRUB_HIDDEN_TIMEOUT is set is no longer supported.
Found linux image: /boot/vmlinuz-4.8.0-52-generic
Found initrd image: /boot/initrd.img-4.8.0-52-generic
Found linux image: /boot/vmlinuz-4.8.0-46-generic
Found initrd image: /boot/initrd.img-4.8.0-46-generic
Found linux image: /boot/vmlinuz-4.8.0-45-generic
Found initrd image: /boot/initrd.img-4.8.0-45-generic
Found linux image: /boot/vmlinuz-4.4.0-78-generic
Found initrd image: /boot/initrd.img-4.4.0-78-generic
Found memtest86+ image: /boot/memtest86+.elf
Found memtest86+ image: /boot/memtest86+.bin
Em minha frustração eu entrei em alguns comandos ( não a abordagem correta, mas todos nós estivemos lá ...), apenas para ver se as coisas iriam responder. Isso não aconteceu. Indo da saída "Found memtest86 + image: /boot/memtest86+.bin" para "done" demorou cerca de 15 minutos. Não faço ideia de por que demora tanto tempo, mas a paciência pode ajudá-lo, isso me fez!