In case someone ends up here with a similar issue, you also end up at the UEFI shell when UEFI is selected for a BIOS-based image.

Try with Advanced -> Boot firmware changed to bios.