Estas instruções são para máquinas regulares da BIOS e não são para máquinas EFI mais recentes.
Você já executou sudo update-grub
após inicializar o Ubuntu? Executar este comando deve atualizar tudo.
Se não, você pode precisar reinstalar o grub no MBR. Execute o seguinte comando para fazer isso:
sudo grub-install /dev/sda
Em seguida, execute sudo update-grub
novamente para uma boa medida.
Além disso, verifique se o grub está instalando no MBR correto no disco correto. Você pode instalar o grub em qualquer MBR em qualquer disco (até mesmo em um drive USB) alterando o comando acima, então tenha isso em mente.
Por favor, poste qualquer erro.