Unable to boot grub/Ubuntu directly after removing Windows partition

At first I kept my Windows 7 partition(s) to be on the safe side but I removed the partition(s) now because I never used Windows any more.
The result is a machine that won't boot into grub/Ubuntu any more. I keep getting the notification that no operating system is found even though I restored grub, as well as the MBR.

Previous partition table:

[ NTFS ][       NTFS       ][[         Ext4         ][ swap ]]

Actions performed:

1. Remove both NTFS partitions


2. Resized only the Ext4 partition


3. Set the boot flag on the Ext4 partition


4. Ran boot-repair from a live disk, as well as restoring grub manually


5. Ran boot-repair to restore the MBR since step 4 wasn't sufficient

System: HP EliteBook 8470w
Error message:

At first I had the impression it might be an UEFI issue, but this is and always has been disabled in the BIOS.

The only way I can get my system running now is by booting from an USB stick with YUMI, which presents me with an option to boot from the first hard drive. Choosing this option finally gives me the grub boot menu and allows me to boot Ubuntu.

What could the problem be and how can I fix it?

Things magically started working about after creating an empty FAT partition of some 200MB as the first partition and doing nothing more after that.

I was in the process of creating an EFI partition just as a test. Despite of what the BIOS was telling me about being in Legacy mode instead of UEFI, I wanted to make sure for myself. For some strange reason no additional steps were required after solely creating the partition. The additional grub steps for converting Ubuntu into UEFI mode weren't needed. Just converting Ubuntu into Legacy mode wasn't an option because the bios_grub flag wasn't available anywhere (Ubuntu live boot with gparted, stand-alone gparted live disc, etc.).