Very strange problem. But my iPhone after an update to 5.0.1 now thinks i thinks it is in the Netherlands so caller id doesn’t work etc.
Here is the fix
In case anyone is still working on getting this fixed for themselves or future folks looking for a fix, I thought I’d post what it took for me to get it working. None of the other fixes seemed to help me move out of The Netherlands. Worst part for me was this default made stored phone numbers not match for Caller ID. Apple support seemed to have no prior knowledge of the issue. After 3+ hours and 5 “specialists” trying various solutions (most of which were posted here and tried by me previously), what finally worked was turning off “International Assist” in Settings > Phone, then (because this appears to be a Verizon issue) dial *228 to update the phone service choosing option 1. Follow this by calling a second time to *228 and select option 2. Once those updates are finished, power off the phone and start it up again. For me, that fixed the problem and I was able to turn the “International Assist” option back on and it was fine (turning it off may have been an be an extra step, but who knows). I wish they had come up with this before having me do a phone reset, but at least it’s working… for now.