This has tripped me up so many times, and the parted invocation needed to fix it is hard to find on google.
The issue is that with GPT, grub won’t have room to embed all of it’s needed files, leading to an unbootable system. The solution is to create a small (1meg is plenty) partition and mark it as space that grub can use.
So here it is:
# parted [block device] set [partition no, from 1] bios_grub on
