Corrupt Backupt GPT Table
Up-front: I'm the author of GPT fdisk (gdisk, sgdisk, and cgdisk), so I understand GPT data structures pretty well.
If Windows is booting in BIOS mode, then it should be booting from an MBR disk. If you've got just one disk, then it looks like Windows is booting in EFI mode, since your one disk uses GPT. (A caveat, though: If your partition table is badly damaged -- say with a hybrid MBR that gdisk is not recognizing for some reason -- it could be it's really a BIOS-mode installation.) I mention this because you said you performed an EFI-mode installation "because [you] couldn't install it in Legacy" mode. Rule #1 of multi-booting these days is to install both OSes in the same mode. In other words, if your Windows installation is in EFI mode, installing Ubuntu in BIOS/CSM/legacy mode is something you should NOT be doing. This may be a bit of a side-track, since it sounds like you did the right thing, but I want to be clear on it because there are a lot of bad procedures out there that suggest installing in BIOS/CSM/legacy mode when that should not be done. I most especially want to make sure that you don't attempt a BIOS/CSM/legacy-mode install to fix your current problem. Absent information that you've really got a BIOS-mode Windows installation, re-installing Ubuntu in BIOS mode would do nothing but create new problems atop the ones you've got now.
Now, to your main problem: I've heard of this sort of thing happening -- that is, gdisk reports a damaged backup partition table, the user fixes it, and it turns up damaged again. The usual cause is that something else is overwriting the backup partition table. Sometimes this is RAID software. Motherboard-based software RAID (often called "fake RAID") can do this because some such systems use space at the end of the disk (where the backup GPT data goes) to store its data. If you've got just one disk, you don't need RAID, so you should disable your RAID settings in your firmware and in all your OSes. Rebooting with and without booting into Windows may help you figure out what's doing the damage, and therefore what you need to adjust. OTOH, if you've got multiple disks and they are being used in a RAID setup, then you need to activate RAID support in Ubuntu. This is covered many places; here seems as good a starting point as any, although I've not read it thoroughly.
Such problems can also occur because of advanced-feature tools like disk encryption or disk compression software. Such tools sometimes dump stuff at the end of the disk, assuming that it's unused. (Under MBR, space after the final partition often goes to waste, so this approach often works. It's not safe, but it often works.) If you've got such tools installed, remove them, or at least research them to figure out if they're compatible with GPT and update or replace them if they aren't GPT-friendly.
If these suggestions don't help, try extracting the last few sectors of the disk to a file with dd. You'll first need to figure out the disk's size in sectors (gdisk will tell you this), then use dd, as in:
sudo dd if=/dev/sda of=foo.img bs=512 skip=100021518
This command copies the contents of the disk, starting at 100021518, to the file foo.img. You'll want to set your skip= value to at least 34 less than the number of sectors on your disk, since GPT normally uses the last 33 sectors. You can then examine the resulting file with hexdump or something similar, as in:
hexdump -C foo.img | less
The idea here is to look for strings or other clues that might tell you what's causing the problems. Of course, you should look at the end of the disk before repairing it. The final 33 sectors should be enough, since that's all that gdisk uses.