An update just stopped my 16.04 laptop from booting

I just sudo apt update and was told no updates found, so I'm fully up to date.

I've just seen a disturbing window pop up:

***
Record your encryption passphrase

To encrypt your home directory or "Private" folder, a strong passphrase has been automatically generated. Usually your directory is unlocked with your user password, but if you ever need to manually recover this directory, you will need this passphrase. Please print or write it down and store it in a safe location. If you click "Run this action now", enter your login password at the "Passphrase" prompt and you can display your randomly generated passphrase. Otherwise, you will need to run "ecryptfs-unwrap-passphrase" from the command line to retrieve and record your generated passphrase."
***

My home directory is encrypted. I've not seen this window pop up since I first installed this installation of 16.04 several months ago. I run firejail firefox and don't think I run any software that's particularly at risk.

Does the system reboot and cold boot OK now?

I'm waiting for a couple of virtualbox VMs to transfer to a USB stick. Then will test.

No it's still broken. I closed everything and shut down. Left it 10 secs and turned back on.

It says:

***
Boot Device Not Found

Please install an operating system on you hard disk.

Hard Disk - (3F0)

F2 System Diagnostics

For more information visit <HP website>
***

I tried F2 and ran a quick HDD check and it passed, I didn't bother with the long test.

I had to ESC again, F9, then boot from EFI file, then select efi>ubuntu>grubx64.efi

no other block / bootable devices are/have been attached while booting. I checked by BIOS and it's as I left it. Secure boot is off. I normally read patch notes / changelog but haven't really the past couple of days. I do think I saw a grub update yesterday but I might be mistaken, The one thing I glanced at in the update that happened today was a patch that said something about secure boot and a warning and a shim? I notice that there's a shim file next to the grubx64.efi boot file.

Well now I'm very confused. I was reading as I don't know much about the first few moments of boot. I ran efibootmgr and got something strange..

Timeout: 0 seconds
BootOrder: 0001,9999,0006
Boot0001* Qubes
Boot0006 Windows Boot Manager
Boot9999* USB Drive (UEFI)

I downloaded qubes, made a usb stick about a 6 weeks ago. I definitely have never had it installed on this machine (I had it on a T420) and I don't think I ever booted from the USB stick on this machine.. but I guess I must have booted from that USB stick just to see how badly it handled a 1440p screen (badly).

I have no idea where ubuntu has gone from that list (I assume it was there?), I certainly haven't had that qubes USB stick near this laptop in a month and have rebooted many times since.

Should I use 'man efibootmgr' to work out how to delete the qubes entry (and windows?) and add a grubx64/shim entry?

I'm still convinced that update from today broke it somehow but it looks like Qubes has something to answer.

I've done

sudo efibootmgr -b 1 -B
sudo efibootmgr -b 6 -B
sudo efibootmgr -c \\EFI\\ubuntu\\grubx64.efi -L Ubuntu

and the output of efibootmgr is as expected with my new changes, 0000 (Ubuntu) is first in order. Still same Boot Device Not Found on reboot.

All I can suggest is to report a bug. Maybe others can advise.