iPhone 5 all outgoing calls fail
Another solution I found to this problem:

Open Settings -&gt; Phone -&gt; Show Caller ID

It'll take some seconds to load the and show a loading indicator, after that is done the phone will be able to make and receive calls