I encountered this mysterious Call Failed issue frequently in my iPhone 5. Usually this happens, at least for me, while I come back to my Home network after roaming
I have tried all means to fix this issue and have failed most of the times. Even I have went to an extent of resetting my iPhone couple of times. Finally I found an easy fix deep inside Apple’s iPhone forum.
The fix is very simple. Dial *#31# in your iPhone. That’s it. Now you can make calls again.
BTW, the contacts and dial pad App in iPhone are crap when compared to Android. I will cover this in detail in another post