sudo update-grub is not affecting the grub menu
Solution 1:
I had the exact same symptoms.
Turned out that the Ubuntu 20.04 installer had incorrectly mounted the Windows 10 EFI partition in /etc/fstab
at /boot/efi
for the Ubuntu installation.
This meant that new kernels and other grub updates were being added to the wrong grub.cfg in the wrong partition.
I just mounted the correct Ubuntu EFI partition in /etc/fstab
and updated grub and bingo, my grub menu was properly updated.
Not sure if this is a bug in the Ubuntu dual boot installer for EFI or just my system.
Hope this is helpful.