[tsac]

Ok so the only thing not tried is doing a reload of the OS. I would do a backup of contacts and other needed data and then do a complete OS reload. Once reloaded with the ( do not add any contacts etc ) new OS try to see if the problem still exists. If all is ok then just add contacts and email and other items. DO NOT do a complete restore as it may put the issue back.
As for the message your getting, it is the message from the carrier. It may be that some type of corruption is causing the dialed phone number to be errored and the system rejects the call. As I have said before I get that in some areas I never did before.

Good luck