I had exactly the same issue installing 16.04 64 desktop on a new SSD with UEFI enabled using USB install media. Unlike in the question I chose to create my own partitions as I had other disks to mount. I hit this error near the beginning of the package installation.
After a bit of googling I found this page:
which states in the General principles section:
if there was not any UEFI partition on your HDD, you first will have to create it
and points to:
Mount point: /boot/efi (remark: no need to set this mount point when using the manual partitioning, the Ubuntu installer will detect it automatically)
Size: minimum 100Mib. 200MiB recommended.
Other: needs a "boot" flag.
So I reinstalled and when I came to partition my drive, I chose the EFI option from the list that includes filesystems and swap etc and made it 200MB at the start of the disk. I did not get the option to select the filesystem or set the bootable flag.
After this the rest of the install went fine.
This is how the partitions on this disk look after the install:
enter image description here
The same information can be seen by running parted:
$ sudo parted /dev/sda
GNU Parted 3.2
Welcome to GNU Parted! Type 'help' to view a list of commands.
Model: ATA Samsung SSD 750 (scsi)
Disk /dev/sda: 250GB
Sector size (logical/physical): 512B/512B
Partition Table: gpt
Number Start End Size File system Name Flags
2 1049kB 200MB 199MB fat32 boot, esp
3 200MB 242GB 242GB ext4
1 242GB 250GB 8000MB linux-swap(v1)
Note that the partition that was created is an EFI System Partition (ESP) and the disk has a GUID Partition Table (GPT) rather than an MBR partition table.
If you look in /boot/efi or /sys/firmware/efi/ on this disk you should find them populated, likewise running sudo efibootmgr should provide real output, see the link below if you want more information.