Após mais 2 dias, finalmente tenho uma solução.
Eu mudei o controlador SATA de AHCI para IDE na minha BIOS, o que tornou o sistema inicializável, mas eu ainda não estava feliz com isso.
Então eu pesquisei um pouco e percebi que o módulo do kernel AHCI não estava carregado, o que explica por que o CD ao vivo e o modo IDE funcionaram.
Então, adicionei o módulo AHCI ao initramfs
:
gksudo gedit /etc/initramfs-tools/modules
No editor de texto, acabei de adicionar ahci
no final do arquivo. Então salvei o arquivo, fechei o editor de texto e executei:
sudo update-initramfs -u
Agora a inicialização funciona bem. Eu acho que vou ter que refazer isso toda vez que houver uma atualização do kernel.