Dude! You just made my life a little simpler
I had the same problem, although I had no problem using web or receiving calls I used to get call failed when making calls with 3g on almost every time.
This time I tried your method going in: Settings / Phone / Show My Caller ID and not doing any thing else, tried making a call with 3g ON and boom it worked!
Seems like the change in network needs to confirm caller ID setting or something
I'm glad I could help you out, it looks like even though this thread is 3 years old it still helps people