Unable to boot UEFI installation

[Marcus Karlsson <mk@acc.umu.se>]

Hello.

I have a problem with installing Debian 7.1 on a machine using UEFI. The
machine does not boot after the installation, instead it shows:

  Reboot and Select proper Boot device
  or Insert Boot Media in selected Boot device and press a key

Just to test a different distribution I decided to blank the drive and
installed Ubuntu 13.04 using UEFI. It worked just fine. Puzzled about
this I blanked the drive again and reinstalled Debian, but with the same
problem as before.

I then booted the machine from the Debian install media, mounted the
EFI boot partition from the shell and made a copy of the debian
directory which I called ubuntu; the same name that Ubuntu used for the
directory where it stored the boot loader. Maybe the machine was still
somehow set to boot the Ubuntu boot loader. This time it worked. The
machine booted into GRUB and successfully loaded Debian. Removing the
ubuntu directory made the machine unable to boot again.

This is the output from efibootmgr:

# efibootmgr -v
BootCurrent: 0000
Timeout: 0 seconds
BootOrder: 0000,0001,0002,0003,0004
Boot0000* debian	HD(1,800,f3800,cc9862e4-6391-4ba2-9105-2692e627993f)File(\EFI\debian\grubx64.efi)
Boot0001* SATA : PORT 4 : TSSTcorp CDDVDW SH-222AB	BIOS(3,0,00)AMBO
Boot0002* SATA : PORT 6G 0 : INTEL SSDSC2CW180A3 : PART 0 : Boot Drive	BIOS(2,0,00)AMBO
Boot0003* SATA : PORT 6G 1 : INTEL SSDSC2CW180A3 : PART 0 : Boot Drive	BIOS(2,0,00)AMBO
Boot0004* UEFI : SATA : PORT 6G 0 : INTEL SSDSC2CW180A3 : PART 0 : OS Bootloader	ACPI(a0341d0,0)PCI(1f,2)03120a000000ffff0000HD(1,800,f3800,cc9862e4-6391-4ba2-9105-2692e627993f)AMBO

Secure boot is not enabled.

Does anyone know why this happens or what I can do about it, apart from
renaming the installed boot loader directory?

Marcus