I have the same problem. Since upgrade from 13.10 to 14.04, I've run Boot Repair which failed. I do recall some issues getting grub working when I originally installed 13.04 but don't have a record of how I got it working. Upgrade from 13.04 to 13.10 went OK.

I've spent the last five hours searching so any suggestions would be greatly appreciated.

When I try to dpkg-reconfigure grub-pc, I get:

chris:~$ sudo dpkg-reconfigure grub-pc
dpkg-query: package 'grub-pc' is not installed and no information is available
Use dpkg --info (= dpkg-deb --info) to examine archive files,
and dpkg --contents (= dpkg-deb --contents) to list their contents.
/usr/sbin/dpkg-reconfigure: grub-pc is not installed.

sudo grub-install runs and does not report any errors.

I've got no installed_devices listed.

chris:~$ sudo debconf-show grub-pc
  grub-pc/partition_description:
  grub2/device_map_regenerated:
  grub-pc/timeout: 10
  grub-pc/disk_description:
  grub-pc/install_devices_failed: false
  grub-pc/install_devices_empty: false
  grub-pc/install_devices:
  grub-pc/postrm_purge_boot_grub: false
* grub2/linux_cmdline_default: quiet splash
  grub-pc/mixed_legacy_and_grub2: true
  grub-pc/kopt_extracted: false
  grub-pc/install_devices_failed_upgrade: true
  grub-pc/hidden_timeout: true
  grub-pc/chainload_from_menu.lst: true
  grub2/kfreebsd_cmdline:
* grub2/linux_cmdline:
  grub2/kfreebsd_cmdline_default: quiet splash
  grub-pc/install_devices_disks_changed:

chris:~$ sudo parted -l
Model: ATA TOSHIBA MQ01ABD1 (scsi)
Disk /dev/sda: 1000GB
Sector size (logical/physical): 512B/4096B
Partition Table: gpt

Number  Start   End     Size    File system     Name                          Flags
 1      1049kB  420MB   419MB   ntfs            Basic data partition          hidden, diag
 2      420MB   735MB   315MB   fat32           EFI system partition          boot
 3      735MB   869MB   134MB                   Microsoft reserved partition  msftres
 4      869MB   248GB   247GB   ntfs            Basic data partition          msftdata
 7      248GB   458GB   210GB   ext4                                          msftdata
 8      458GB   966GB   508GB   ntfs                                          msftdata
 6      966GB   982GB   16.0GB  linux-swap(v1)
 5      982GB   1000GB  18.3GB  ntfs            Basic data partition          hidden, diag

chris:~$ dpkg-query -l 'grub*'
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend
|/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad)
||/ Name               Version        Architecture   Description
+++-==================-==============-==============-==========================================
un  grub               <none>         <none>         (no description available)
ii  grub-common        2.02~beta2-9   amd64          GRand Unified Bootloader (common files)
un  grub-coreboot      <none>         <none>         (no description available)
un  grub-doc           <none>         <none>         (no description available)
un  grub-efi           <none>         <none>         (no description available)
ii  grub-efi-amd64     2.02~beta2-9   amd64          GRand Unified Bootloader, version 2 (EFI-A
ii  grub-efi-amd64-bin 2.02~beta2-9   amd64          GRand Unified Bootloader, version 2 (EFI-A
ii  grub-efi-amd64-sig 1.34+2.02~beta amd64          GRand Unified Bootloader, version 2 (EFI-A
un  grub-efi-ia32      <none>         <none>         (no description available)
un  grub-efi-ia64      <none>         <none>         (no description available)
un  grub-emu           <none>         <none>         (no description available)
un  grub-ieee1275      <none>         <none>         (no description available)
un  grub-legacy        <none>         <none>         (no description available)
un  grub-legacy-doc    <none>         <none>         (no description available)
un  grub-linuxbios     <none>         <none>         (no description available)
un  grub-pc            <none>         <none>         (no description available)
un  grub-xen           <none>         <none>         (no description available)
un  grub-yeeloong      <none>         <none>         (no description available)
un  grub2              <none>         <none>         (no description available)
ii  grub2-common       2.02~beta2-9   amd64          GRand Unified Bootloader (common files for