In case anyone else runs into this issue: if you have another VPN on an Android phone set to Always-on, Nebula Android will fail to connect with a VPN permissions error. Took me a bit to realize what was going on. Said something like "allow VPN permissions when requested" but permissions had never been requested.
From Jeff Wright on Slack:
https://definednetworking.slack.com/archives/CS01XE0KZ/p1681145123777509