Happy to post more details if necessary/useful. I've tried obvious things (boot-repair etc.).

Summary

By default, the only way I can currently boot my machine is by inserting the Ubuntu (14.04) stick I created to install a dual-boot system alongside Windows 8.1. A couple of required manual steps are described below. Also described below are the steps I can take to enable a successful reboot without the USB stick, however these settings do not persist, and fail after a second reboot. The question is: how can I make my UEFI settings persist across reboots?

Initial situation: boot failure and workaround

If the stick is not inserted, boot fails (after the option to enter the settings menu) with a "please insert correct media and reboot" type message.

With the drive inserted, I can access the (USB) grub command line and then get to the installed grub configuration via:

configfile (hd1,gpt2)/EFI/ubuntu/grub.cfg

The second grub menu then enables booting Ubuntu or the original Windows 8.1 instance.

Apparent fix: grub-install and efibootmgr

If I take the following two steps, I can obtain a successful reboot to the installed grub menu (no USB stick required):

1) sudo grub-install --efi-directory=/boot/efi --target=x86_64-efi --uefi-secure-boot

2) sudo efibootmgr -n 0

Note, ubuntu is entry 0000 (and active) in efibootmgr output.

After these steps, efibootmgr -v yields similar output regarding the Ubuntu installation before and after one reboot (but only one), namely:

BootOrder: 0000,0005,0004,0001,0002

Boot0000* ubuntu HD(2,96800,32000,e3ae99c8-b2d4-4941-94cf-58a12eec0c21)File(\EFI\ubuntu\shimx64.efi)

But, a second reboot fails (if the two commands above are not executed) and now requires the USB stick again. After the second reboot, efibootmgr -v yields:

Boot0000 ubuntu Vendor(99e275e7-75a0-4b37-a2e6-c5385e6c00cb,)

No longer active and no longer correctly configured.

Suggestions? Again, happy to post further details if that helps.

First, look for an updated firmware from your manufacturer. (It will probably be listed as a "BIOS update," although it's not really a BIOS.) After updating, you'll have to re-register GRUB with efibootmgr. With any luck it will start working; however, don't get your hopes up, since these updates seldom do any good.

Another option that sometimes works is to set the default boot option via Windows. You can do this by opening an Administrator's Command Prompt window and typing:

bcdedit /set {bootmgr} path \EFI\ubuntu\shimx64.efi

If neither a firmware update nor setting the Ubuntu boot loader as the default using Windows helps and the computer is new, I strongly suggest you return it to the store for a refund, on the grounds that the behavior you're seeing is a design defect. Manufacturers will continue delivering machines with that sort of defect if they don't feel the pain of doing so, and the only way they'll feel any sort of pain is if machines are returned and they know why.

If the machine is too old to be returned for a refund, your only choice is an ugly shell game with boot loader filenames, as I describe on this page of mine. This is most easily done via Boot Repair, which provides an option to do such renaming and reconfigure GRUB appropriately on its Advanced menu. The option is called something like "back up and rename EFI boot files" (but that's from memory; the exact wording is almost certainly something slightly different).