I setup my Verizon iPhone 4S by restoring from a backup of my 3GS.
Now my contact's phone numbers aren't formatted at all. They now look like
5555551234 whereas they used to be formatted like
In the Messages app, most conversations are no longer linked to a contact's name, only phone numbers are shown.
Creating a new contact exhibits the same problem.
+1 to the beginning of each contact's phone number(s) seems to help, but I'd rather not have to manually edit all of my contacts.