I’ve just switched from iOS to GrapheneOS a few days ago on Pixel 6a, and I’ve been facing the same problem since the beginning.
Today I’ve figured out that there is another notification settings here:
Settings > Apps > Special app access > Device & app notifications
Here the only allowed app was the Launcher. And the GPS was under the Not allowed header.
I’ve just allowed notification access for GPS as well, however I don’t know yet whether this will work. And I don’t know whether this will cause any security issues which we avoid from.
There are some detailed sub settings under this menu such as Real-time, Conversations (SMS etc), Notifications… And at the bottom, you can click on See all apps and choose the apps you want to activate for this settings.