Pouco antes de eu estar prestes a devolver as máquinas eu queria tentar mais uma vez (depois de 24 horas). Para minha surpresa, ambas as máquinas foram inicializadas desta vez. Há definitivamente algum tipo de bug em algum desses códigos uefi que consultam o status da bateria.
Enfim, eu estou feliz que as máquinas estão de volta e eu acho que não vou tentar instalar o Ubuntu nativamente em um momento previsível.
Última atualização para o registro: Eu não pude resistir e tentei instalar o Ubuntu novamente um mês depois. Eu fui com 14.04 imagem diária e optou por usar o disco inteiro (limpou o Windows, não dual-boot), e desta vez funcionou.