O que acontece é que o particionamento adotado nesse disco é GPT ao invés de MSDOS.
É o que a mensagem de erro do post inicial está dizendo:
"warning: this GPT partition label contains no BIOS Boot Partition;"
É possível usar GPT, que originalmente foi criado para EFI, mesmo num sistema PC/BIOS.
A vantagem do GPT é que permite um número enorme de partições (128), ao contrário do MSDOS que permite apenas 4 partições primárias ou 3 primárias e 1 estendida. A outra vantagem é que GPT consegue trabalhar com partições maiores que 2 TiB (terabytes).
Se subir o sistema através de um live-iso (pendrive ou cdrom) e usar o comando:
sudo parted -l
(sinal de hífen mais letra ele no final do comando acima)
deverá ser possível confirmar isso, confirmar que se trata de GPT.
É por essa razão que o /Creto/ indicou aquela sequência de comandos mencionada.
Poderia refazer o particionamento para o MBR convencional, como sugerido pelo /filipe2005rj/ no post #3, mas aí vai cair nas limitações acima mencionadas, enfim, depende do que pretende fazer e do disco no caso concreto.
Experimente gravar o grub usando um software especialista, talvez seja mais fácil.
O Boot-Repair é uma opção, existem outras.
Não sei dizer ao certo se o Boot-Repair irá identificar essa condição GPT no disco e fazer a gravação corretamente, se o caso verifique nele também nas opções avançadas (não tenho aqui no momento para poder conferir), mas enfim, experimente para ver se faz:
Suba o sistema pelo live-iso, abra um terminal e faça:
sudo add-apt-repository ppa:yannubuntu/boot-repair
sudo apt-get update
sudo apt-get install -y boot-repair && boot-repair