TL; DR How do I create an EFI system partition from scratch? How do I put the EFI firmware on it onces it is created?

Long version

I hava Toshiba T430 laptop. I received it with Windows 7 installed (but I think originally it has shipped with Windows 8). I installed Ubuntu on it, but deleted some partitions on the disk so that I ended up wiping out the Windows and only having Ubuntu. Among the deleted partitions was the EFI System partition. I discovered that Ubuntu now boots in Legacy mode (and not UEFI). I am trying to follow this guide on converting my Ubuntu installation from Legacy to UEFI. The problem - since there is no EFI partition whenever I choose from BIOS to boot using UEFI I cannot boot. That counts not only for the harddrive, but usb and DVD as well. I think this is logical - it expects an EFI partition and since it can't find it, it cannot continue booting futher, be it from HDD or DVD. So how do I recreate the EFI partition?

The guide above says:

Creating an EFI partition

If you are manually partitioning your disk in the Ubuntu installer, you need to make sure you have an EFI partition set up.

1. If your disk already contains an EFI partition (eg if your computer had Windows8 preinstalled), it can be used for Ubuntu too. Do not format it. It is strongly recommended to have only 1 EFI partition per disk.

2. An EFI partition can be created via a recent version of GParted (the Gparted version included in the 12.04 disk is OK), and must have the following attributes:

   1. Mount point: /boot/efi (remark: no need to set this mount point when using the manual partitioning, the Ubuntu installer will detect it automatically)

   2. Size: minimum 100Mib. 200MiB recommended.

   3. Type: FAT32

   4. Other: needs a "boot" flag.

I had some trouble creating this partition:

• I boot from a live Ubuntu DVD, open GParted, create a 200MB partition and format it to FAT32.
• In GParted I cannot set the mount point and thus cannot set the bootflag.
• I didn't set the mount point in /etc/fstab since it's a live CD and fstab looked quite differently from what I expected compared to a normal boot. Anyway, I just didn't know what values to set.

I booted again via the live DVD and then chose to install Ubuntu. I then created a partition with the mentioned criteria - mount point, 200MB, FAT32, boot flag.

However, I continue to have this problem and I suppose it's because on that partition there is no EFI firmware, it's just an empty partition, which is suitable to have EFI firmware.

So again, how do I create an EFI partition, which has the EFI software, so that the laptop can once again boot in UEFI mode?