Meu palpite é que suas variáveis do sistema EFI não estão sendo definidas para apontar para o bootloader correto. O programa que você deseja verificar isso é efibootmgr . Isso mostrará todas as entradas de inicialização armazenadas na NVRAM.
Em teoria, grub-install deve lidar com isso, mas você pode não estar passando as opções corretas. Este exemplo de comando DEVE funcionar:
grub-install --target=x86_64-efi --efi-directory=ESP_MOUNT_PATH --bootloader-id=grub
Altere ESP_MOUNT_PATH para o caminho do seu diretório EFI.
Se isso não funcionar, você pode tentar usar efibootmgr diretamente:
efibootmgr --create --disk /dev/sda --part 1 --loader /EFI/ubuntu/grubx64.efi --label "GRUB"
Eu acho que em alguns sistemas você pode ter que usar /EFI/ubuntu/shimx64.efi . Então tente algo assim e veja o que funciona.