Ubuntu – How to Dual boot Ubuntu 12.04 and Windows 8

Fair disclosure: I don't fully understand the mechanics involved. Still, after experiencing a similar nightmare with my laptop, what finally did it for me was realizing that I can't install grub too far into the drive; You don't say what partitioning scheme you tried, so I figured this might be the issue you're experiencing as well.

What I did was keep the UEFI structure intact (or, rather, allowing the Windows installation disc to create a new one from scratch), but I made sure to have a small (200MB) dedicated partition located relatively close to the beginning of the drive (around 400MB into it) which Windows leaves alone. (I can't stress enough, though, that it should still be Windows that partitions the drive. The way I did it, I completely removed the filesystem, then created a 400MB partition, my dedicated partition after it, then erased the original and let Windows do its thing with what's left. I'm sure you could simplify the process somehow, but I was seeing stars by that stage.)

Then, after Windows was done making a clean install in the rest of the space allotted to it (and, in the process, creating the necessary UEFI structure before my partition, and a Windows partition immediately after), I simply replaced that partition with an ext4 partition during the Ubuntu installation and mounted it as /boot, installing grub to it. Everything worked fine after that (after running boot-repair, that is).