Comment 22 for bug 1355698

Ok so had a quite similar bug : https://bugs.launchpad.net/elementaryos/+bug/1355290

What I did :

Installed Elementary again ;

My Elementary partition is in /dev/sda4
My EFI is in /dev/sda1

Chose "Install partition boot to /dev/sda".

I installed with wifi ON, there was NO error.

Then I typed in a terminal (based on this method http://howtoubuntu.org/how-to-repair-restore-reinstall-grub-2-with-a-ubuntu-live-cd ) :
sudo mount /dev/sda4 /mnt
sudo mount /dev/sda1 /mnt/boot/efi # (I mounted the efi as grub did it when it was working in Ubuntu)

sudo mount --bind /dev /mnt/dev &&
sudo mount --bind /dev/pts /mnt/dev/pts &&
sudo mount --bind /proc /mnt/proc &&
sudo mount --bind /sys /mnt/sys

sudo chroot /mnt

grub-install --verbose --efi-directory=/mnt/boot/efi --boot-directory=/mnt/boot --no-secure-boot-efi --target=x86_64-efi /dev/sda
grub-install --recheck --verbose --efi-directory=/mnt/boot/efi --boot-directory=/mnt/boot --no-secure-boot-efi --target=x86_64-efi /dev/sda
update-grub

It seems like the "no secure boot" feature was of most importance here.