Installed/Updated Windows 8 UEFI after Ubuntu - Restore GRUB

So, I had a laptop with Windows 8 OEM copy obviously installed in UEFI configuration with GPT partitioning. A little while ago I installed Ubuntu 13.xx(the latest one) alongside it and GRUB fortunately detected Windows and everything was fine until now.

So yesterday, I updated to Windows 8.1 and it apparently rewrote the boot-loader and quite naturally I cannot boot into Ubuntu. It takes me straight to Windows.

How do I repair GRUB? Most of the help pages/articles talk about MBR partitioning which is quite different case from UEFI+GPT AFAIK. And the articles that do talk about UEFI are about fixing non-bootable Windows installation after installing linux which is not my case.

Any tried and tested method to get Ubuntu up again?

PS: Before you recommend it, No; EasyBCD or similar tools cannot add linux to Windows bootloader if Windows is installed with UEFI.

Using Boot Repair, as MariusMatutiae suggests, may work; however, that program sometimes does more than is wise, so I prefer to avoid it. There are at least three less radical solutions:

Solution 1: Use the Firmware

Many EFIs provide a built-in boot manager that enables you to adjust the boot order. Your Ubuntu/GRUB entry probably still exists, so all you need to do is to adjust the boot order using the firmware. The trouble with this approach is that the EFI setup utilities vary so much that it's impossible to provide universally-applicable instructions for how to do this. If your firmware supports this feature, though, it's likely to be the simplest way to do it -- once you figure out how to get to the option!

Solution 2: Use bcdedit in Windows

The Windows bcdedit tool can add a non-Windows boot loader to the boot list. The trick is figuring out what the file is. You can do it this way:

1. Boot to Windows
2. Open an Administrator Command Prompt window. (Don't use a third-party shell for this, either; I've seen reports that bcdedit won't work correctly with some of them.)
3. Type mountvol S: /S to mount the ESP as S:. (You can change S: to something else if you like.)
4. Using the Command Prompt, check S: to locate your Ubuntu boot loader. It's probably either S:\EFI\ubuntu\grubx64.efi or S:\ubuntu\shimx64.efi. If you see the latter, it should be safe to use it, and it may be necessary to use it -- shim is how Ubuntu deals with Secure Boot (SB), but on a non-SB computer, it will have little effect. If Secure Boot is inactive, then shim may or may not be installed, so you may need to refer to grubx64.efi directly.
5. Type bcdedit /set {bootmgr} path \EFI\ubuntu\shimx64.efi, changing shimx64.efi to grubx64.efi if shimx64.efi isn't present. Change the path if it's something else, which is unlikely.
6. Optionally, type bcdedit /set {bootmgr} description "Ubuntu" to set the name that appears in the EFI's own boot manager list. Change Ubuntu to whatever you like.

If you already know the filename for your boot loader, you can skip steps #3 and #4. (The ESP doesn't need to be mounted to use bcdedit in this way.)

This method has the advantage that it keeps Windows from messing with the boot order -- sometimes Windows will try to adjust the boot order unbidden. I don't know if this would prevent a repeat of this problem if/when you upgrade to whatever comes after Windows 8.1, though.

Solution 3: Boot to Linux and Use efibootmgr

You can probably boot to Linux by using the firmware's own boot manager, which you can access on most computers by hitting Esc or a function key at boot time, although which key varies from one computer to another. Alternatively, you may be able to use rEFInd on a USB flash drive or CD-R as a boot manager if yours is inadequate. You can also boot using a Linux live CD or emergency disk, but be sure you boot in EFI mode -- a BIOS-mode boot won't be adequate. Once you're in Linux, you can use efibootmgr to adjust the boot order:

1. Open a Terminal window.
2. Type sudo efibootmgr -v to obtain a list of boot programs. One will be for Linux, and will launch either shim or GRUB. Note the BootOrder list. Chances are the Windows entry is now first, and the Ubuntu entry comes later in the list. Some entries may be confusing. Just ignore them; focus on finding the Ubuntu entry and identifying its number (in the Boot#### entry at the start of the line).
3. Type sudo efibootmgr -o {list}, changing {list} to a comma-separated list of boot numbers, as in sudo efibootmgr -o 5,0 if Boot0005 is for Ubuntu and Boot0000 is for Windows. You can add more entries if you like, but the first one is the most important, since that's what will be booted first.

If an Ubuntu entry does not exist, you can create one with efibootmgr, as in:

efibootmgr -c -d /dev/sda -p 1 -l '\EFI\ubuntu\shimx64.efi' -L "Ubuntu"

Change -d /dev/sda to point to your whole-disk device and -c 1 to specify the partition number. (In fact, /dev/sda and 1 are the defaults, so you really need these only if your ESP is not /dev/sda1.)