I have a bit of time to try to sort this out. I'll look into borrowing a phone or reinstalling stock if I can't get it working on Graphene soon.
I don't have a Google account, and would rather not get one, so I can't easily test if logging in would fix it.
Google Play Services has network permission. As I mentioned, I also tried enabling all permissions for it temporarily.
I'll try to post an issue on GitHub. It would be great if the devs could make this work effortlessly in future versions, to save others this difficulty. I don't know if I should expect a fix quick enough to help me, though, so I'm still interested in hearing workaround ideas.