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:
https://help.ubuntu.com/community/UEFI#General_principles
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:
https://help.ubuntu.com/community/UEFI#Creating_an_EFI_System_Partition
Which states:
- 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.
- Type: FAT32
- 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 to select the filesystem or set the bootable flag.
After this the rest of the install went fine.