You are in Brazil (so am I), so you can't just dial the "+" in front of the country code. You need to dial "00" and the CSP (the long distance operator code).
What happens is that some operators (Oi and Claro, for sure) have a JavaCard application in the SIM card that intercepts every call you place and before send the dialed number to the network verifies if you are in a situation that you should need to add a CSP or not, and adds the operators own CSP in that case, if there isn't one in the dialed number.
So, for example, if I'm in Rio (area code 21) and dial a call to (24) 9999-8888, which is a long distance call, the application will add "0"+ to my number. The same if I'm in Petrópolis (area code 24), since my MSISDN is from Rio.
On the other side, if I register my phone numbers using the international notation, the application is smart enough to remove the "+" and the country code and add the "0" and the CSP, unless it realizes that you're roaming abroad.
Besides Oi and Claro, I would guess that Vivo also uses an application like that, since it buys SIM cards from the same manufacturers.
TIM has a different application in their SIM cards that modifies the phone numbers in your SIM card to add the CSP 41. It is a lame solution and I regret every time I have to use a TIM mobile.
If it is enough for you to have an application like TIM's, there are at least two in the brazilian App Store that will edit the iPhone's Address Book:
- [Minha Operadora](http://itunes.apple.com/br/app/minha-operadora/id401640256?mt=8)
- [DDD Fácil](http://itunes.apple.com/br/app/ddd-facil/id381994693?mt=8)
I haven't tested either, so I can't offer advice on how well they work.
Otherwise, you will probably have to go back to an operator that offer that application in the SIM card (there is no way for a user to add apps to their SIM card by themselves).
No. The app doesn't currently have an override and simply takes the distance units from the system settings.
It surely would be nice to have finer control, but the code isn't there to make a change today.
Best Answer
When I was writing this question and was in Language & Region, I tried setting the iPhone Language even though I didn't expect it to do anything. It was already set to English but I went ahead and selected "English (US)". It went to a black screen that said "Setting Language" (or something similar) for a while and when it was done all the phone numbers are displaying correctly. So I guess it's possible the language wasn't set to "English (US)" but I can't imagine why. Anyway, since I already went through the effort of editing the screenshots and writing the question I figured I'd leave this here in case it's helpful to someone.