I experienced call failed problem before whenever I start or reset my iPhone and it continues for a few hours. During this time, I can't make any outgoing calls, but ingoing calls and SMS are working fine.

I just got this fixed by turning off the call forwarding and call waiting option in the iPhone. Not sure how it is related to my problem but it got my problem fixed as for now.