I also used to think that if stock works, Graphene should work fine too... I find it baffling. My guess would be that the carrier wants to fingerprint the OS in some way (e.g. to activate services... no matter how invasive this is), and somehow fails.
As I said, the phone seems to be compatible, I have made lengthy calls with it and received calls using the stock OS, call forwarding works too. Everything seems to work.
I'll try the resetting, thanks for the tip.
I have actually tried the stock Phone app, and the same thing happened. It occurred to me that I could perhaps try using Google servers instead of the Graphene ones (in the network settings), but I have a hunch that's not what's wrong.
Does it make any difference if I flash Graphene with the SIM card in vs out? Btw, the SIM card is not a very recent one, and it's running out of storage space (which has not been an issue so far).