Comment 3 for bug 1617721

Workaround:
sudo apt-get purge grub\*
sudo apt-get install grub-efi
sudo apt-get autoremove
sudo update-grub

Source:
http://askubuntu.com/a/763984/170127:

Output:
$ sudo apt-get purge grub\*
Reading package lists... Done
Building dependency tree
Reading state information... Done
Note, selecting 'grub-legacy' for glob 'grub*'
...
...
...
Package 'grub2-themes-ubuntu-mate' is not installed, so not removed
The following package was automatically installed and is no longer required:
  shim
Use 'sudo apt autoremove' to remove it.
The following packages will be REMOVED:
  grub-common* grub-efi-amd64* grub-efi-amd64-bin* grub-efi-amd64-signed* grub2-common* shim-signed*
0 upgraded, 0 newly installed, 6 to remove and 0 not upgraded.
1 not fully installed or removed.
After this operation, 20.8 MB disk space will be freed.
Do you want to continue? [Y/n] y
(Reading database ... 226018 files and directories currently installed.)
Removing grub-efi-amd64-signed (1.66.2+2.02~beta2-36ubuntu3.2) ...
Removing grub-efi-amd64 (2.02~beta2-36ubuntu3.2) ...
Purging configuration files for grub-efi-amd64 (2.02~beta2-36ubuntu3.2) ...
Removing shim-signed (1.18~16.04.1+0.8-0ubuntu2) ...
Purging configuration files for shim-signed (1.18~16.04.1+0.8-0ubuntu2) ...
Removing grub2-common (2.02~beta2-36ubuntu3.2) ...
Removing grub-efi-amd64-bin (2.02~beta2-36ubuntu3.2) ...
Removing grub-common (2.02~beta2-36ubuntu3.2) ...
TPurging configuration files for grub-common (2.02~beta2-36ubuntu3.2) ...
Processing triggers for man-db (2.7.5-1) ...
Processing triggers for install-info (6.1.0.dfsg.1-5) ...
$ sudo apt-get install grub-efi
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following package was automatically installed and is no longer required:
  shim
Use 'sudo apt autoremove' to remove it.
The following additional packages will be installed:
  grub-common grub-efi-amd64 grub-efi-amd64-bin grub2-common
Suggested packages:
  multiboot-doc grub-emu xorriso desktop-base
The following NEW packages will be installed:
  grub-common grub-efi grub-efi-amd64 grub-efi-amd64-bin grub2-common
0 upgraded, 5 newly installed, 0 to remove and 0 not upgraded.
Need to get 2,546 B/2,939 kB of archives.
After this operation, 16.1 MB of additional disk space will be used.
Do you want to continue? [Y/n] y
Get:1 file:/home/samjnaa/ab/orig_amd64_a-g grub-common 2.02~beta2-36ubuntu3.2 [1,707 kB]
Get:2 file:/home/samjnaa/ab/orig_amd64_a-g grub2-common 2.02~beta2-36ubuntu3.2 [511 kB]
Get:3 file:/home/samjnaa/ab/orig_amd64_a-g grub-efi-amd64-bin 2.02~beta2-36ubuntu3.2 [653 kB]
Get:4 file:/home/samjnaa/ab/orig_amd64_a-g grub-efi-amd64 2.02~beta2-36ubuntu3.2 [65.7 kB]
Get:5 http://ubuntu.mirror.lrz.de/ubuntu xenial-updates/main amd64 grub-efi amd64 2.02~beta2-36ubuntu3.2 [2,546 B]
Fetched 2,546 B in 2s (928 B/s)
Preconfiguring packages ...
Selecting previously unselected package grub-common.
(Reading database ... 225632 files and directories currently installed.)
Preparing to unpack .../grub-common_2.02~beta2-36ubuntu3.2_amd64.deb ...
Unpacking grub-common (2.02~beta2-36ubuntu3.2) ...
Selecting previously unselected package grub2-common.
Preparing to unpack .../grub2-common_2.02~beta2-36ubuntu3.2_amd64.deb ...
Unpacking grub2-common (2.02~beta2-36ubuntu3.2) ...
Selecting previously unselected package grub-efi-amd64-bin.
Preparing to unpack .../grub-efi-amd64-bin_2.02~beta2-36ubuntu3.2_amd64.deb ...
Unpacking grub-efi-amd64-bin (2.02~beta2-36ubuntu3.2) ...
Selecting previously unselected package grub-efi-amd64.
Preparing to unpack .../grub-efi-amd64_2.02~beta2-36ubuntu3.2_amd64.deb ...
Unpacking grub-efi-amd64 (2.02~beta2-36ubuntu3.2) ...
Selecting previously unselected package grub-efi.
Preparing to unpack .../grub-efi_2.02~beta2-36ubuntu3.2_amd64.deb ...
Unpacking grub-efi (2.02~beta2-36ubuntu3.2) ...
Processing triggers for systemd (229-4ubuntu11) ...
Processing triggers for ureadahead (0.100.0-19) ...
ureadahead will be reprofiled on next reboot
Processing triggers for man-db (2.7.5-1) ...
Processing triggers for install-info (6.1.0.dfsg.1-5) ...
Setting up grub-common (2.02~beta2-36ubuntu3.2) ...
update-rc.d: warning: start and stop actions are no longer supported; falling back to defaults
Setting up grub2-common (2.02~beta2-36ubuntu3.2) ...
Setting up grub-efi-amd64-bin (2.02~beta2-36ubuntu3.2) ...
Setting up grub-efi-amd64 (2.02~beta2-36ubuntu3.2) ...
Creating config file /etc/default/grub with new version
Installing for x86_64-efi platform.
efibootmgr: EFI variables are not supported on this system.
efibootmgr: EFI variables are not supported on this system.
Installation finished. No error reported.
Generating grub configuration file ...
Warning: Setting GRUB_TIMEOUT to a non-zero value when GRUB_HIDDEN_TIMEOUT is set is no longer supported.
Found linux image: /boot/vmlinuz-4.4.0-43-generic
Found initrd image: /boot/initrd.img-4.4.0-43-generic
Found linux image: /boot/vmlinuz-4.4.0-28-generic
Found initrd image: /boot/initrd.img-4.4.0-28-generic
Found memtest86+ image: /boot/memtest86+.elf
Found memtest86+ image: /boot/memtest86+.bin
Found Ubuntu 14.04.5 LTS (14.04) on /dev/sda4
done
Setting up grub-efi (2.02~beta2-36ubuntu3.2) ...
Processing triggers for systemd (229-4ubuntu11) ...
Processing triggers for ureadahead (0.100.0-19) ...
$

Hmm it seems only the grub-efi-amd64-signed *signed* package that causes the problem.