Hi -thanks for your post. I just switched over to Verizon and iPhone 4s from Tmobile with a Blackberry.
I am having the same problem you have described and have not been able to find a soloution online (nor that many people complaining about it surprisingly).
I am wondering if you have found a solution to this issue yet, its quite important for me as over half my calls are international. Thanks