It is almost certainly a DNS issue, considering that websites do not resolve but fixed services like Signal and the Play Store are still able to connect.
All I can suggest is to double-check your router settings, as well as your VPN settings and any ad-blocking/tracker-blocking services on your phone or otherwise (Adguard, Pi-hole server, etc.).
Just to make sure your router isn't doing anything funky, verify that you have free IP address allotments in your router's DHCP settings. By default, GrapheneOS generates a random MAC address each time it connects to a network, which can mean a new IP is assigned every single time. If your DHCP lease times are too long and IP allotments too little, you'll run out of available IP addresses for your phone. This shouldn't cause the symptoms you're experiencing, but some routers are weird.