I deleted my EFI partition.

[Ponch0]

No bootable device found - when booting from UEFI.

I tried dual boot installing Linux Mint 14 Mate with Windows 8 and in doing so I chopped up my Win8, there were just bits and pieces of it, here and there. I initially tried the recovery disk and it did not help at all it just made the situation worse. So, I came across a suggestion to install Linux Mint 14 KDE, it gives the option of installing over the entire disk, I did not realize however, (it didn't click) that I would delete the EFI partition. By the way, I don't care at this point that I lost my Win8, I would just like to be able to boot Mint from UEFI.

I came across this post https://help.ubuntu.com/community/UEFI
There's a section in there that explains how to create a partition. I followed the steps, created Gparted LiveCD and booted from it, the problem I'm having is that I can't split the main disk and create a seperate partition from it at all. Are there any alternatives, a program that I can run from KDE that works in CSM boot, that will allow me to create an EFI partition. Am I following the wrong post? What can I do?

(KDE Partition Manager doesn't allow me to create new partitions either)

My machine is the Toshiba S855-S5378.

Thank you