Comment 5 for bug 1904263

Just ran an apt update/upgrade today on my home desktop and had the same issue.

----
The following NEW packages will be installed
  libapparmor1:i386
The following packages will be upgraded:
  alsa-ucm-conf grub-common grub-efi-amd64-bin grub-efi-amd64-signed grub-pc grub-pc-bin grub2-common libasound2 libasound2:i386 libasound2-data libasound2-dev
  libatopology2 libpulse-dev libpulse-mainloop-glib0 libpulse0 libpulse0:i386 libpulsedsp pulseaudio pulseaudio-module-bluetooth pulseaudio-utils
  yaru-theme-gnome-shell yaru-theme-gtk yaru-theme-icon yaru-theme-sound
24 to upgrade, 1 to newly install, 0 to remove and 0 not to upgrade.

...
Preparing to unpack .../15-grub-pc_2.04-1ubuntu26.7_amd64.deb ...
Unpacking grub-pc (2.04-1ubuntu26.7) over (2.04-1ubuntu26.6) ...
Preparing to unpack .../16-grub2-common_2.04-1ubuntu26.7_amd64.deb ...
Unpacking grub2-common (2.04-1ubuntu26.7) over (2.04-1ubuntu26.6) ...
Preparing to unpack .../17-grub-pc-bin_2.04-1ubuntu26.7_amd64.deb ...
Unpacking grub-pc-bin (2.04-1ubuntu26.7) over (2.04-1ubuntu26.6) ...
Preparing to unpack .../18-grub-efi-amd64-signed_1.142.9+2.04-1ubuntu26.7_amd64.deb ...
Unpacking grub-efi-amd64-signed (1.142.9+2.04-1ubuntu26.7) over (1.142.8+2.04-1ubuntu26.6) ...
Preparing to unpack .../19-grub-efi-amd64-bin_2.04-1ubuntu26.7_amd64.deb ...
Unpacking grub-efi-amd64-bin (2.04-1ubuntu26.7) over (2.04-1ubuntu26.6) ...
Preparing to unpack .../20-grub-common_2.04-1ubuntu26.7_amd64.deb ...
Unpacking grub-common (2.04-1ubuntu26.7) over (2.04-1ubuntu26.6) ...

...
grub-install: warning: Internal error.
grub-install: error: failed to register the EFI boot entry: Operation not permitted.
Processing triggers for systemd (245.4-4ubuntu3.3) ...
Processing triggers for man-db (2.9.1-1) ...
Processing triggers for dbus (1.12.16-2ubuntu2.1) ...
Processing triggers for install-info (6.7.0.dfsg.2-5) ...
Processing triggers for libc-bin (2.31-0ubuntu9.1) ...

EFI Partition is also pretty big, for what it is.
------
Model: ATA Samsung SSD 840 (scsi)
Disk /dev/sda: 250GB
Sector size (logical/physical): 512B/512B
Partition Table: gpt
Disk Flags:

Number Start End Size File system Name Flags
 1 1049kB 538MB 537MB fat32 EFI System Partition boot, esp
 2 538MB 250GB 250GB ext4
-----

Tried removing and reinstalling. No specific failures noted from running grub-update outside the script. Files got updated

root@pinhead:/boot/grub/x86_64-efi# ls -l /boot/efi/EFI/BOOT/
total 4088
-rwx------ 1 root root 1681280 Nov 23 18:58 BOOTX64.EFI
-rwx------ 1 root root 1222800 Nov 23 18:21 fbx64.efi
-rwx------ 1 root root 1277024 Nov 23 18:21 mmx64.efi

root@pinhead:/boot/grub/x86_64-efi# cat /boot/efi/EFI/ubuntu/grub.cfg
search.fs_uuid 48221d77-53ec-48c0-ab30-bffb0b0129ec root hd0,gpt2
set prefix=($root)'/boot/grub'
configfile $prefix/grub.cfg

root@shodan-pin:/boot/grub/x86_64-efi# cat /boot/efi/EFI/ubuntu/BOOTX64.CSV
shimx64.efi,ubuntu,,This is the boot entry for ubuntu

root@pinhead:/boot/grub/x86_64-efi# ls -l /boot/efi/EFI/ubuntu/
total 4212
-rwx------ 1 root root 108 Nov 23 18:21 BOOTX64.CSV
-rwx------ 1 root root 126 Nov 23 18:58 grub.cfg
-rwx------ 1 root root 1681280 Nov 23 18:58 grubx64.efi
-rwx------ 1 root root 1277024 Nov 23 18:21 mmx64.efi
-rwx------ 1 root root 1341560 Nov 23 18:21 shimx64.efi

root@pinhead:/boot/grub/x86_64-efi# grub-install --no-uefi-secure-boot
Installing for x86_64-efi platform.
grub-install: warning: Internal error.
grub-install: error: failed to register the EFI boot entry: Operation not permitted.

Also reported here: https://bugs.launchpad.net/ubuntu/+source/grub2/+bug/1901650