Presence of a Linux partition causes FileVault2 setup to fail
Solution 1:
I believe I found the issue: Apple expects 128 MiB of free space between every partition. Disk Utility hides this free space, similar to how it hides the ESP. If this padding isn't present, it generates the error I described above.
Easy fix: Tell Gparted to use +128 MiB as the beginning offset for each partition.
Edit: Nevermind, this only solves the "Verify Disk" problem...I still can't enable FileVault. See above for an update.