How old is the SIM?
As I understand, there have been some changes recently in Android’s management of SIMs which may lead to problems especially with older cards.
See for example:
Solved with a new SIM issued at no cost (after demonstrating in the shop that a new SIM worked correctly).