Eu tenho exatamente o mesmo problema com o notebook MSI GE40 2OC. A BIOS / EFI é a American Megatrends Aptio com a última atualização de 2013-07-12 (versão 10F). Uma ligeira diferença está no tamanho na última linha "Tentando alocar em 0x0-0xffffffffffffffff alinhado 0x1 tamanho 0x1345000", que é no meu caso 0x1344000.
Minha atual (bastante hacky) solução é mudar na BIOS o modo legado (para linux) e o modo UEFI (para win8 pré-instalado) antes de mudar o sistema operacional no qual preciso trabalhar. Como as alterações feitas pelo GRUB no MBR durante a instalação no modo herdado não influenciam a inicialização do UEFI, isso funciona. No entanto, é uma dor, para ir ao BIOS para alternar OS.
A última linha parece ser do grub2, então talvez eu relate um bug mais tarde.