Another update for anyone in the same situation:
As I said before the PlanetCom tech support told me to try to flash from a Windows machine, using virtualbox since I have no access to a physical Windows box. They also said that reformatting was probably not needed, and if the Windows flash did not work that I would have to send in my device.
With very low expectations I set up a Windows 7 vm (using KVM/virt-manager) and attempted to flash. I only got more error messages...
Well, fuck it, I thought. Lets reformat (as per shuntcap's instructions), so on my Linux box I formatted and tried to flash. More error messages!! Something about bad XRAM or something like that. But as a very last attempt, I tried reflashing from the Windows machine, and lo and behold! It worked! The Gemini now booted into Linux!
However, I realized that I had forgotten to add the NVRAM to the Windows flash, so I tried another flash from Linux (where I had the NVRAM backup), and now it worked without a problem!
The moral of the story? The flash tool seems to be a very fickle beast...
Thanks for the help, everyone!