Solution is to use a bios_grub partition, which is not the same as the /boot partition.
By default the bios_grub partition is 1MiB, and it must be flagged bios_grub. Mine is the first partition on my disk. If your partition 2 is actually /boot as parted suggests, that would not be correct and you should make another 1MiB partition.
With GPT and GRUB2 the minimum filesystem has three partitions: bios_grub, root, swap. (not perfectly sure swap is required)
Why does grub fail to boot after simply running "grub-install"?
Unknown... You'd think it wouldn't modify anything if it says clearly it cannot embed so it can't work.
Why does it say "file not found"?
/vmlinuz is a symlink that uses the boot partition, and the boot partition is corrupt. The bios_grub code was written on top of its ext3 structure. This probably meant that /boot was not mounted, and the grub files seen there were actually on the root system, which didn't contain the kernel.
Why doesn't grub want to install without this setting I set with parted
A GPT partition table has no space for a bootloader, unlike MBR. So a specific partition must be created to hold the boot code. Before running "grub-install", specify this partition with the command:
parted /dev/sda set 1 bios_grub on
I thought all I needed was a separate /boot. How does the Ubuntu CD installer install it without the bios_grub setting?
This requirement seems to be all that is needed for the Ubuntu installer, but it creates an unstandard system which is broken easily.
When GRUB says "This GPT partition label has no BIOS Boot Partition", it means the bios_grub partition, not /boot.
An hour of googling was 5 minutes short to find the answer... anyway:
gdisk and sgdisk allow to relocate the second GPT header in "expert mode".
If the basic situation was like this:
# sgdisk -p /dev/sda
Disk /dev/sda: 3902341120 sectors, 1.8 TiB
Logical sector size: 512 bytes
Disk identifier (GUID): 01BFC515-C093-495B-A33F-CA925FB74357
Partition table holds up to 128 entries
First usable sector is 34, last usable sector is 1951170526
Partitions will be aligned on 2048-sector boundaries
Total free space is 6042 sectors (3.0 MiB)
Number Start (sector) End (sector) Size Code Name
1 2048 8388641 4.0 GiB 0700
2 8390656 16777249 4.0 GiB 0700
3 16779264 1951170526 922.4 GiB 8E00
(note the last usable sector is 1951170526)
By using the x command in gdisk and then e command, the partition table looks like this:
Expert command (? for help): p
Disk /dev/sda: 3902341120 sectors, 1.8 TiB
Logical sector size: 512 bytes
Disk identifier (GUID): 01BFC515-C093-495B-A33F-CA925FB74357
Partition table holds up to 128 entries
First usable sector is 34, last usable sector is 3902341086
Partitions will be aligned on 2048-sector boundaries
Total free space is 1951176602 sectors (930.4 GiB)
Number Start (sector) End (sector) Size Code Name
1 2048 8388641 4.0 GiB 0700
2 8390656 16777249 4.0 GiB 0700
3 16779264 1951170526 922.4 GiB 8E00
(note the last usable sector is 3902341086)
After that, removing and re-creating a larger partition works without a problem.
Best Answer
If you (somehow) remember/backed up the previous PT, then just recreating it with the same layout should cut it IF you did not write to the disk. Otherwise, all bets are off.