My wife has an iPhone 4s on the Verizon network. After I did an over the air (OTA) upgrade to 5.0.1, the phone would only show the phone number for the people that was texting and calling her (even though their contact information was still in the contact app).
Here is how I fixed the issue:
1) Open the Phone and dial *228. This is a Verizon over-the-air programming number.
2) When the system answers press 1 for “Program or activate your phone”
3) Wait for the call to disconnect. You should get a prompt stating something like, “Settings updated.”
4) Dial *228 again.
5) When the system answers press 2 for updating your roaming capabilities
6) Wait for the call to disconnect. You should get a prompt stating something like, “Settings updated.”
7) Open the Settings App.
8) In your mail and contact settings, delete the account(s) that you use to sync your contacts. This could be iCloud, Gmail (via Exchange), etc.
9) Open the Task Manager (double click the home button) and kill the open Applications by long tapping one of the icons. When the icons begin to shake, tap the red circle with the minus sign.
10) Turn off the iPhone. Then turn it back on.
11) Open the Settings App.
12) In your mail and contact settings, add back the account(s) that you deleted in step 8.
13) Wait a few minutes (3-5mins)
14) Open the Message App and Recent calls list to verify the fix.
Others have tried this fix:
1) Open the Settings App
2) Go to General > International > Language
3) Set the phone language to British English
4) Open the Task Manager (double click the home button) and kill the open Applications by long tapping one of the icons. When the icons begin to shake, tap the red circle with the minus sign.
5) Turn off the iPhone. Then turn it back on.
6) Open the Settings App
7) Go to General > International > Language
8) Set the phone back to US English