Latest package upgrades, specifically kali-desktop-base and kali-desktop-gnome, have triggered an update-grub which now uses a UUID that's nowhere to be found.

#########################################
error: no such device: 67c96667-XXXX-XXXX-9925-XXXXXXXXXXX
error: disk lvmid/XCQNAr-XXXX-XXXX-XXXX-XXXX-XXXX-wVjfbh/XXXXXX-XXXX-XXXX-XXXX-XXXX-mAe8-XXXX' not found.
error: file '/grub/themes/kali/background.png' not found.

Press any key to continue...
#########################################

output of /var/log/apt/history.log [truncated]

Start-Date: 2020-07-13 09:06:18
Commandline: apt full-upgrade
Requested-By: XXX (1000)
Install: zsh-autosuggestions:amd64 (0.6.4-1, automatic), libmatroska7:amd64 (1.6.0-2, automatic), libebml5:amd64 (1.4.0-2, automatic), libdav1d4:amd64 (0.7.1-3, automatic), zsh-syntax-highlighting:amd64 (0.7.1-2, automatic)
Upgrade: vlc-bin:amd64 (3.0.11-1, 3.0.11-3+b1), gnome-control-center-data:amd64 (1:3.36.3-1, 1:3.36.4-1), vlc-plugin-video-output:amd64 (3.0.11-1, 3.0.11-3+b1), libavformat58:amd64 (7:4.3-2, 7:4.3-3), libavfilter7:amd64 (7:4.3-2, 7:4.3-3), dos2unix:amd64 (7.4.0-2, 7.4.1-1), kali-themes:amd64 (2020.2.3, 2020.3.0), gnome-control-center:amd64 (1:3.36.3-1, 1:3.36.4-1), vlc-plugin-samba:amd64 (3.0.11-1, 3.0.11-3+b1), kali-desktop-base:amd64 (2020.2.3, 2020.3.0), kali-desktop-core:amd64 (2020.3.4, 2020.3.6), libswresample3:amd64 (7:4.3-2, 7:4.3-3), vlc-plugin-qt:amd64 (3.0.11-1, 3.0.11-3+b1), libctf-nobfd0:amd64 (2.34-8, 2.34.90.20200706-1), kali-tools-top10:amd64 (2020.3.4, 2020.3.6), binutils:amd64 (2.34-8, 2.34.90.20200706-1), vlc-plugin-skins2:amd64 (3.0.11-1, 3.0.11-3+b1), vlc-plugin-visualization:amd64 (3.0.11-1, 3.0.11-3+b1), vlc-l10n:amd64 (3.0.11-1, 3.0.11-3), vlc-plugin-notify:amd64 (3.0.11-1, 3.0.11-3+b1), libvlc5:amd64 (3.0.11-1, 3.0.11-3+b1), kali-desktop-gnome:amd64 (2020.3.4, 2020.3.6), libpostproc55:amd64 (7:4.3-2, 7:4.3-3), libvlccore9:amd64 (3.0.11-1, 3.0.11-3+b1), libvlc-bin:amd64 (3.0.11-1, 3.0.11-3+b1), binutils-x86-64-linux-gnu:amd64 (2.34-8, 2.34.90.20200706-1), libllvm10:amd64 (1:10.0.0-4, 1:10.0.1~+rc4-1), libavcodec58:amd64 (7:4.3-2, 7:4.3-3), vlc:amd64 (3.0.11-1, 3.0.11-3+b1), commix:amd64 (3.0-20191111-0kali1, 3.1-0kali1), libavutil56:amd64 (7:4.3-2, 7:4.3-3), vlc-data:amd64 (3.0.11-1, 3.0.11-3), libswscale5:amd64 (7:4.3-2, 7:4.3-3), binutils-common:amd64 (2.34-8, 2.34.90.20200706-1), vlc-plugin-video-splitter:amd64 (3.0.11-1, 3.0.11-3+b1), libbinutils:amd64 (2.34-8, 2.34.90.20200706-1), kali-themes-common:amd64 (2020.2.3, 2020.3.0), kali-linux-default:amd64 (2020.3.4, 2020.3.6), kali-linux-core:amd64 (2020.3.4, 2020.3.6), libical3:amd64 (3.0.8-1+b1, 3.0.8-2), metasploit-framework:amd64 (5.0.97-0kali1, 5.0.98-0kali1), vlc-plugin-base:amd64 (3.0.11-1, 3.0.11-3+b1), python3-mistune:amd64 (0.8.4-2, 0.8.4-3), libavresample4:amd64 (7:4.3-2, 7:4.3-3), less:amd64 (551-1, 551-2), libctf0:amd64 (2.34-8, 2.34.90.20200706-1)
End-Date: 2020-07-13 09:08:13
#########################################

output of /var/log/apt/term.log [truncated]

Unpacking vlc-plugin-visualization:amd64 (3.0.11-3+b1) over (3.0.11-1) ...
Setting up libebml5:amd64 (1.4.0-2) ...
Setting up zsh-autosuggestions (0.6.4-1) ...
Setting up binutils-common:amd64 (2.34.90.20200706-1) ...
Setting up less (551-2) ...
Setting up libctf-nobfd0:amd64 (2.34.90.20200706-1) ...
Setting up vlc-l10n (3.0.11-3) ...
Setting up metasploit-framework (5.0.98-0kali1) ...
Setting up libavutil56:amd64 (7:4.3-3) ...
Setting up libllvm10:amd64 (1:10.0.1~+rc4-1) ...
Setting up gnome-control-center-data (1:3.36.4-1) ...
Setting up libpostproc55:amd64 (7:4.3-3) ...
Setting up libvlccore9:amd64 (3.0.11-3+b1) ...
Setting up vlc-plugin-qt:amd64 (3.0.11-3+b1) ...
Setting up libmatroska7:amd64 (1.6.0-2) ...
Setting up zsh-syntax-highlighting (0.7.1-2) ...
Setting up kali-themes-common (2020.3.0) ...
Setting up libical3:amd64 (3.0.8-2) ...
Setting up libdav1d4:amd64 (0.7.1-3) ...
Setting up libswscale5:amd64 (7:4.3-3) ...
Setting up dos2unix (7.4.1-1) ...
Setting up kali-desktop-base (2020.3.0) ...
grub-efi* packages found, using 16/9 as default grub background ratio
update-alternatives: using /usr/share/grub/themes/kali/grub-16x9.png to provide /usr/share/images/desktop-base/desktop-grub.png (desktop-grub) in auto mode
Generating grub configuration file ...
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
Found theme: /boot/grub/themes/kali/theme.txt
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
Found background image: /usr/share/images/desktop-base/desktop-grub.png
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
/dev/sdb: open failed: No medium found
Found linux image: /boot/vmlinuz-5.7.0-kali1-amd64
Found initrd image: /boot/initrd.img-5.7.0-kali1-amd64
Found linux image: /boot/vmlinuz-5.6.0-kali2-amd64
Found initrd image: /boot/initrd.img-5.6.0-kali2-amd64
#########################################

grub.cfg

if [ x$feature_default_font_path = xy ] ; then
font=unicode
else
insmod lvm
insmod ext2
set root='lvmid/XCQNAr-XXXX-XXXX-XXXX-XXXX-XXXX-wVjfbh/XXXXXX-XXXX-XXXX-XXXX-XXXX-mAe8-XXXX'
if [ x$feature_platform_search_hint = xy ]; then
search --no-floppy --fs-uuid --set=root --hint='lvmid/XCQNAr-XXXX-XXXX-XXXX-XXXX-XXXX-wVjfbh/XXXXXX-XXXX-XXXX-XXXX-XXXX-mAe8-XXXX' 67c96667-XXXX-XXXX-9925-XXXXXXXXXXX
else
search --no-floppy --fs-uuid --set=root 67c96667-XXXX-XXXX-9925-XXXXXXXXXXX
fi
font="/usr/share/grub/unicode.pf2"
fi
#########################################

$ sudo blkid

/dev/nvme0n1p1: UUID="0969-XXXX" BLOCK_SIZE="512" TYPE="vfat" PARTUUID="b9a318e8-XXXX-46b6-XXXX-XXXXXXXXXXXX"
/dev/nvme0n1p2: UUID="7d197849-XXXX-XXXX-90f9-XXXXXXXXXXXX" BLOCK_SIZE="1024" TYPE="ext2" PARTUUID="00d56f77-XXXX-458e-XXXX-XXXXXXXXXXXX"
/dev/nvme0n1p3: UUID="2b4ef47d-XXXX-46bd-XXXX-XXXXXXXXXXXX" TYPE="crypto_LUKS" PARTUUID="df0e3be4-XXXX-XXXX-8aa7-XXXXXXXXXXXX"
/dev/sda1: UUID="B7B4-XXXX" BLOCK_SIZE="512" TYPE="vfat" PARTUUID="5b1d17ac-XXXX-XXXX-a41b-XXXXXXXXXXXX"
/dev/sda2: UUID="d8bdd326-XXXX-468f-XXXX-XXXXXXXXXXXX" BLOCK_SIZE="4096" TYPE="ext4" PARTUUID="26397cb5-XXXX-XXXX-95af-XXXXXXXXXXXX"
/dev/sda3: UUID="e8accccd-XXXX-XXXX-b240-XXXXXXXXXXXX" TYPE="swap" PARTUUID="b74c5696-XXXX-4634-XXXX-XXXXXXXXXXXX"
/dev/mapper/nvme0n1p3_crypt: UUID="FR6aGR-XXXX-XXXX-XXXX-XXXX-zGDK-XXXXXX" TYPE="LVM2_member"
/dev/mapper/XXX--vg-root: UUID="67c96667-XXXX-XXXX-9925-XXXXXXXXXXXX" BLOCK_SIZE="4096" TYPE="ext4"
/dev/mapper/XXX--vg-swap_1: UUID="77c0a7a5-XXXX-XXXX-814c-XXXXXXXXXXXX" TYPE="swap"
#########################################

$ sudo cat /etc/fstab

<file system> <mount point> <type> <options> <dump> <pass>

/dev/mapper/XXX--vg-root / ext4 errors=remount-ro 0 1

/boot was on /dev/nvme0n1p2 during installation

UUID=7d197849-XXXX-XXXX-90f9-XXXXXXXXXXXX /boot ext2 defaults 0 2

/boot/efi was on /dev/nvme0n1p1 during installation

UUID=0969-XXXX /boot/efi vfat umask=0077 0 1
/dev/mapper/XXX--vg-swap_1 none swap sw 0 0
#########################################

This Kali installation is on the NVMe M.2 with LUKS encryption.