Well, I don't have Windows 8 and I don't have UEFI or GPT, but I did have a problem somewhat similar to yours with Windows 7 a few years ago (caused by Windows 7 itself, not by installing Linux to dual boot, by the way), and I used the Windows Recovery DVD and the Microsoft bootrec.exe command from the Windows command line to fix the boot sector and the Windows BCD. The following tutorial indicates that bootrec.exe from a Windows 8 Recovery disc can also fix some Windows BCD problems in the case of Windows 8. So you might want to try that:Fixing Windows 8: Common BCD errors can be fixed using bootrec.exe
I hope it helps. Good luck.