Resolveu eventualmente.
Tive que entrar no BIOS e desabilitar o Quick Boot. Não entendo por que isso quebrou, mas funcionou.
Depois de instalar o Ubuntu 13.10, só posso carregar o GRUB se tiver o LiveUSB que usei conectado.
O que acontece é que eu recebo uma tela preta com "Read Error". Para contornar este erro, inicializando com o USB conectado, o GRUB carrega completamente e sai. Eu nem preciso ter que inicializar manualmente o USB.
Eu tentei duas soluções sem sorte.
sudo grub-install sda
Boot-Repair
Nem resolve meu problema.
Novo log de reparo de inicialização
Algumas coisas a serem observadas:
Edit: É bem tarde agora. Eu vou estar indo para a cama, então vou responder a qualquer resposta sempre que puder.
Resolveu eventualmente.
Tive que entrar no BIOS e desabilitar o Quick Boot. Não entendo por que isso quebrou, mas funcionou.