boot - GRUB2 issue after removing windows and reinstalling ubuntu

Short version
Cannot restore EFI partition with boot repair. Create a proper partition AND put a /EFI/ folder into it, then used boot repair

Original question

I originally had a dual boot with win 8 on it. Deleting it also bricked my EFI boot partition. I eventually reinstalled Ubuntu 14.04 via a live USB as my kernel images were ruined by boot-repair, hoping this would also fix the boot, but that didn't work.

My current partition status:

where sda3 is the former windows partition, and sda6 contains data (backed up). sda2 holds my ubuntu install.

edit
I removed sda1 and placed the bios_grub flagged partition at the start of the disk, reinstalled grub and updated, but to no avail
/edit

My current boot status is given here:

http://paste.ubuntu.com/11774252/

Despite this, if I boot without my live usb in, I only get a black (non grub) screen stating that all boot option have been tried.

I can manually boot the sda2 ubuntu by running grub from the usb key in UEFI mode, pressing c to get the CLI interface, and using

grub> linux (hd1,gpt2)/vmlinuz root=/dev/sda2
grub> initrd (hd1,gpt2)/initrd.img
grub> boot

Then, I tried both using boot-repair and installing grub manually by

sudo grub-install /dev/sda
sudo update-grub

both end up fine with no errors, but I still get the black screen.

Also, I am unable to boot the system manually if a run my grub on the usb key in non UEFI mode, since I cannot reach the Command Line Interface in this case (holding shift leads to a crappy grub GUI and I am stuck there).

I managed to solve it , it was pretty silly.

I used boot-repair to restore the EFI partition.

I created a FAT32 partition of 230mb at the head of the disk and flagged it as boot using gparted. After this, the boot-repair was still complaining about missing the EFI partition ("Your system boot is in efi mode but no efi partition was found. You might want to try again after creating a efi partition(fat32,~100-200mb,head of disk, boot flag)"

Apparently, it is not enough to have the partition as required by the error message. So just did this:

sudo mount /dev/sda4 /media
sudo mkdir /media/EFI

then boot repair correctly found sda4 to be the partition to installe the EFI grub and all worked fine.

I don't know if it is relevant, but I also installed the package grub-efi-amd64-signed at some point.