GrapheneOS
Did you already reset cellular settings via Settings > System > Reset? Did you already try powering off the device and then turning it back on again rather than just a reboot?
I had similar issues with a Pixel 8. I didn't even know that you could reset just the cellular network. Now connectivity is back for both eSim and physical Sim. Thanks GrapheneOS devs for providing this feature!
Thank you @randomp7user for mentioning it!