Como resolvi isso:
Essencialmente, a única maneira sensata que encontrei de consertar isso foi reinstalar completamente o sistema operacional. Consegui fazer uma exportação das configurações anteriores do meu enigmail (incluindo a chave) e, posteriormente, importá-lo para um cliente diferente. Eu mudei do Ubuntu 16.04 para o Kubuntu 16.04, então deve haver pouca diferença por trás das cenas, lá.
De qualquer forma, é isso. Se você está tendo um problema semelhante e não quer reinstalar, tente fazer uma nova pergunta. Desculpe por não fornecer uma solução mais limpa.