Your description of the Windows boot failure is quite vague, so it's not clear if the problem is in GRUB's handoff to the Windows boot loader (which should be fixable in Linux) or in some subsequent Windows-specific step (which would require fixing using a Windows recovery disc). If the former, you might try a USB flash drive or CD-R of my rEFInd boot manager. (One caveat: You'll need to either disable Secure Boot or jump through extra hoops to get rEFInd to boot with Secure Boot active.) If rEFInd can get both Windows and Linux to launch, you can install its Debian-package version in Ubuntu. rEFInd will then take over from GRUB as your primary boot manager.
EDIT: The boot configuration data (BCD) is data that the Microsoft boot loader uses to help with the boot process. I'm foggy on the details, but you can think of it as being roughly analogous to GRUB's configuration file, grub.cfg. Thus, your error message definitely indicates that the problem is on the Windows end -- although it's entirely possible that the file was accidentally deleted or damaged by Linux. I recommend you try using a Windows recovery disc (I have no URLs; try Googling for one, but be cautious -- something from some random Web site might be malware!) or post on a Windows forum for advice.
One more comment: There's a chance that the problem was caused by the Windows 8 (if that's what you're running) Fast Startup feature, which turns a shutdown into a suspend-to-disk operation. This means, among other things, that filesystems (including the ESP's FAT) are not properly shut down, so that when they're accessed from Linux, they can be damaged; and when you reboot into Windows, it will be confused by the changes made by Linux. Thus, it's critical that you disable Fast Startup. Various Web pages describe how to do this, like this one. Note that the Windows Fast Startup feature is completely different from any "fast boot" or "fast startup" feature you might set or disable in the firmware, so don't think that you've dealt with the issue by adjusting your firmware.