JeremyB Duckduck Suave If you disabled location rerouting, turn that back on to use the default configuration where apps using Google Play location have it routed through the OS. If you want to use the Google Play network location service, multiple steps are required.
If you're using the OS location service, that's entirely satellite-based location (GNSS) with support from PSDS and SUPL. If you disabled PSDS and/or SUPL, undo that. PSDS is quite essential and are just static database downloads. If you have network filtering blocking these services, get rid of that. Satellite-based location will not generally work indoors.
None of you has said whether you're testing indoors. None of you has said how you have things configured including whether you're using the Google Play network location service or not. There's no reason to think any of this has to do with an update or a GrapheneOS issue. It's very likely a configuration issue you have. May not be at all the same problem either.