I recommend you read up a bit on how EFI works, since your question reveals a number of common misunderstandings, largely caused by applying BIOS assumptions to the EFI world. Adam Williamson posted a useful blog post on this subject, so that's a good start. The introduction to my page on EFI boot loaders for Linux is another site that can be a useful starting point.
The most critical point to understand is that under EFI, disks are not bootable in the same sense that they are under BIOS. EFI boot loaders are stored as files on a FAT partition known as the EFI System Partition (ESP). A single ESP can house any number of boot loaders. The computer decides which boot loader to use based on its own boot manager's entries, which are stored in NVRAM. You can manipulate those entries in any number of ways, such as by using the bcfg
command in an EFI shell or the efibootmgr
utility in Linux. The better EFIs also provide a user interface so that you can make changes from their setup tools.
Chances are your firmware update erased or re-ordered your NVRAM entries. Thus, you may need to re-create a working entry or at least change the boot order. See here or here for some basic information on how to do this with efibootmgr
. In theory, the Boot Repair program you've tried should be able to do this; but it sometimes doesn't work. Also, Boot Repair must be run from an EFI-mode boot in order to do this properly. This is one of the hurdles that can be difficult to overcome, since many users accidentally boot in BIOS mode rather than in EFI mode.
My rEFInd boot manager can be helpful because it works only in EFI mode. If you download the USB flash drive or CD-R image and boot with it, you'll be guaranteed of booting rEFInd in EFI mode (or not at all). It should then detect your Linux installation -- but since you use LVM, you may need to either boot via the GRUB option or hit F2 or Insert twice and enter a correct root=
option to boot a Linux kernel directly. Once you've booted Linux, you can use efibootmgr
to re-enable GRUB or you can install the Debian-package version of rEFInd to use it from your hard disk.