Passei dias mexendo com isso e pesquisando uma resposta, e não consegui encontrar uma até hoje. Eu queria postar a solução aqui porque acho improvável que eu seja a única (essa questão tem muitos pontos de vista).
A resposta para mim foi encontrada aqui:
A inicialização de um LiveCD e a alteração do grub.cfg para acessar o dispositivo de bloco pelo nome, em vez de pelo UUID, foi a solução para mim. Isso foi temporário ... depois que atualizei meus pacotes, ele instalou uma atualização do grub que o quebrou. Eu tenho mexido com o grub.cfg para tentar corrigi-lo agora, mas seu progresso! Espero que alguém possa preencher o próximo passo.