Por via das dúvidas, alguém se depara com esse tipo de problema ao instalar o Ubuntu com uma instalação existente do UEFI Windows 8, finalmente consegui instalar o Ubuntu usando um DVD.
Me deparei com essa solução lendo um comentário em algum fórum em que alguém tinha o mesmo problema ao iniciar a instalação a partir de um USB como eu, acho que o problema é que o Windows 8 não funciona bem com unidades USB na inicialização.
Eu peguei um dvd, gravei a imagem do ubuntu iso nele com InfraRecorder e reiniciei meu pc, então optei por inicializar do DVD das opções do dispositivo de inicialização do meu PC e o processo de instalação foi suave.
Eu nem tinha o Modo Legado ativado, o que não era o caso quando eu estava tentando instalar a partir de um USB.
Antes de decidir usar um LiveDVD, eu teria que habilitar o modo Legacy no BIOS do meu PC antes que eu pudesse obter opções para inicializar a partir de um USB, o que ainda não funcionava.
Então, eu recomendarei a qualquer pessoa que tente instalar o Ubuntu a partir de um USB com problemas para também dar uma instalação a partir de um LiveDVD antes de desistir de todo o processo. Espero que isto ajude.