Não importa o que eu fiz, o meu compaq evo510s não aceitaria o USB como uma unidade inicializável, ele dizia que era uma mídia inválida. Eu acabei por instalar o Ubuntu usando outro computador para fazê-lo.
Eu conectei o disco rígido da Compaq a outra máquina (uma já rodando o Ubuntu instalado pelo USB), inicializei o USB e instalei na unidade da Compaq. Eu substituí o HDD e agora o Compaq está rodando o Ubuntu!