An EFI System Partition (ESP) is simply a FAT32 partition with a GUID type code of C12A7328-F81F-11D2-BA4B-00A0C93EC93B (or 0xEF on an MBR disk). Most partitioning tools have some other way of displaying the GUID type code, because GUIDs are so cumbersome. In parted, GParted, and most other libparted-based tools, it's shown as a "boot flag" being set on the partition. (Note, however, that in libparted-land, the "boot flag" on a GPT disk is unrelated to the "boot flag" on an MBR disk. AFAIK, libparted provides no way to correctly label an MBR ESP.) In GPT fdisk (gdisk, sgdisk, and cgdisk), an ESP has a type code of EF00. Non-Linux tools have their own ways to identify ESPs.

Thus, to create a new ESP, you would:

1. Boot to any Linux tool that lets you partition the disk. This could be your existing Linux installation or an emergency disk/live CD -- but if you use your regular installation, be aware that you may be limited in what you can do, because many partitioning tools limit what you can do to a disk with partitions that are mounted.


2. Launch the partitioning tool of your choice.


3. If necessary, create a new partition. I recommend making it at least 550MiB in size. Note that you may need to shrink existing partition(s) to make room.


4. Place a FAT32 filesystem on the partition. Some tools, such as GParted, make it possible to combine this step with the previous one.


5. Mark said partition as an ESP.


6. Unmark or delete the old ESP.


7. If necessary, save your changes.

For making partition table changes, there's no need to be concerned with your boot mode -- you can use EFI mode or BIOS mode as you see fit. (That said, some computers make it easier to boot from USB or CD-R in one mode or another.)

I agree with oldfred that creating a new ESP is unlikely to be necessary in your scenario. If you want to completely erase the Windows boot loader from the ESP, feel free to do so -- it would be the /boot/efi/EFI/Microsoft directory tree once Ubuntu is installed. Note that this will not remove the Windows boot loader from the firmware's boot manager menu. To do that, you'll need to use efibootmgr, as in:

$ sudo efibootmgr 

Timeout: 10 seconds

BootOrder: 0000,0004,0001,0002

Boot0000* rEFInd boot manager

Boot0001* PATA: HP DVD Writer 1040r     

Boot0002* SATA: ST32000542AS             2

Boot0003* SATA: TOSHIBA DT01ACA300       3

Boot0004* Windows boot manager

Boot0008* INTERNAL EFI SHELL: ST32000542AS

$ sudo efibootmgr -B -b 4

This example deletes boot option #4, which is identified as "Windows boot manager." (I don't recall the name that Windows uses by default; I edited this example from one of my systems on which Windows is not installed.)