Acontece que o problema foi causado pelo grub-mkconfig travando com a mensagem de erro Generating grub configuration file ...
ERROR: cannot determine partition label for rootfs /dev/sda9
(sda9 segurou minha raiz fs).
O Apt travou porque, quando tentou instalar novos kernels, correu o grub-mkconfig para adicioná-los ao menu de inicialização. Não foi realmente um problema com o apt, mas com o grub.
Eu o consertei reinstalando o Ubuntu e usando o ext3 ao invés do ext4 para a partição que contém a raiz do meu sistema de arquivos. Meu diretório pessoal ainda está em sua própria partição ext4, portanto ele não parece ser afetado.
A resposta do 0x450 funciona bem como uma correção temporária para que se possa usar o apt novamente. Não resolve o problema da raiz.