Increase the EFI System Partition size slightly to ensure that it's at least 512MiB, not just 512MB.  See LP #1306164.