Just wanted to quickly add my name to the people who are finding this a problem. I just had to spend half an hour searching the internet to find out why I couldn't send a text message to my boss that he was expecting. This is not just frustrating and annoying, but also has implications for my future employment so I'd really be very interested in getting a solution to this problem.
I experimented with the reboot suggestion and found that it was successful 3 out of 3 when the Contacts App was closed and failed to resolve the format when Contacts remained open again 3 out of 3. Granted a small sample.
I also tried a "Reset Settings" which did not resolve the phone number format as it returned again within a day..
The final option is the full factory reset and then restore unless anyone has a less time consuming suggestion.
Just done a full reset and restore on my iPhone and the problems returned within a few hours. I have tried everything on this problem now. No help from virgin About this so will be requesting my PAC and try another provider to see if this will fix the issue as it seems to be a virgin network fault.
I came across this thread when trying to troubleshoot this issue for a friend. On his third visit to an Apple Store the person attending to him shouted to a colleague a description of the issue. The immediate response was "is he with Virgin?" My friend then changed networks. That was over a month ago and the problem has not appeared again.