Unfortunately I can't offer a solution, but chiming in to say that I have set up two Pixel 6a phones with GrapheneOS and both have the same issue, which persists after trying all troubleshooting steps in this and the other thread, switching networks and Google accounts, and reinstalling the whole OS.
The only thing that worked was restoring the stock OS. This is definitely a bug or misconfiguration in Graphene, but I have given up investigating it for now.