We'll assume the problem is SIM-based, but just to make sure, take out the SIM card and try it in another phone to confirm.
Also, try another SIM in your iPhone and see.
As for solutions?
1) Go to an econet shop
That's all I got.
For the above commenter prattling about jailbreaks etc ... if the phone is jailbroken, there are no 'components' needed to enable it to make calls out.
If the jailbreak was in order to UNLOCK the phone, using ultrasn0w or whatever, that's it ... once the SIM card can register on the network, it's done.