Consegui resolver o problema.
A linha superior do teclado tem as teclas brilho e volumes, etc., como primárias, e as teclas de função (F1, F2, etc.) disponíveis ao pressionar a tecla "Fn". Então eu fui para a BIOS e os troquei. Acontece que o LiveCD não gostou disso. Isso obviamente causa um conflito de hardware, que por algum motivo se manifesta como um erro Radeon (não tenho idéia do porquê).
De qualquer forma, funciona agora.
Espero que isso ajude as pessoas tentando reinstalar o Ubuntu: Certifique-se de que seu BIOS está configurado para as configurações de fábrica!