We seem to be seeing this type of issue on very large / (root) partitions. Yann in Boot repair highlights it and one solution is a separate small /boot within the first 100GB.
But I normally install with the entire / in a 25GB partition and have not had any real issues. It also may be related to BIOS issues but we cannot seem to tell. Is BIOS in AHCI, IDE, or LBA or large or whatever your BIOS may call it. If IDE it may be emulating the old IDE drives that can only boot from the first 137GB of a drive.
I have often suggested just shrinking / to 100GB or less and for many that seems to have worked. You can then use rest of drive as /home or for data partitions.
=================== sdb1: Location of files loaded by Grub: ====================
GiB - GB File Fragment(s)
872.167018890 = 936.482205696 boot/grub/core.img 1
872.186882019 = 936.503533568 boot/grub/grub.cfg 1
0.907226562 = 0.974127104 boot/initrd.img-3.2.0-23-generic 2
1.875976562 = 2.014314496 boot/initrd.img-3.2.0-29-generic 2
9.555664062 = 10.260316160 boot/initrd.img-3.2.0-30-generic 2
10.157226562 = 10.906238976 boot/initrd.img-3.2.0-31-generic 2