Ubuntu 16 MATE - UEFI - no bootable medium after install

I used the default ‘Erase disk and Install Ubuntu MATE’
The installer said it sets up 3 partitions - one for boot, one main and one swap.

At some point the installer asks if I want to install MP3 (and other restricted software), saying that I should check a box to disable safe boot and setup a key. I did that too…

Now I redid the install, and didn’t check that box.
After install, I have a different message:
"Default Boot Device Missing or Boot Failed
Insert Recovery Media and Hit any key
Then Select ‘Boot Manager’ to choose a new Boot Device or to boot Recovery Media’