None of the above solutions worked for the problem that I was having regarding this... I finally found a solution which follows below:
I ran into a incredbily frustrating problem recently whereby any number that I attempted to turn into a new contact, either using the "Add Contact" button under SMS / iMessages or the "Create New Contact" button under the Recently Called list (Recents), would not appear in my phone's main Contact list or in my Contacts app.
The detail information added simply did not show up.
After banging my head against the wall, taking my phone to the Genius Bar only to have them tell me there was not solution, banging my head against the wall again... I finally found a solution!!
In order to fix this problem:
1) Go into "Settings"
2) Go into "General"
3) Scroll to "Reset"
4) Select "Reset All Settings"
The phone will prompt you indicating that all your settings will be lost but your data will remain.
5) Authoirze the "Reset"
The phone will power down, take a few minutes to power back up and voilà the next time you add add a contact from SMS / iMessages or from your recently called list it will work as it's supposed to!
... at least it did for me ( ;
NOTES:
This is for an AT&T iPhone
In my research on trying to determine why this happens, I discovered that it happens to Verizon phones as well but the problem is caused by a completely different bug and the solution is consequetnely completely different. For that problem search for *228 and you'll find what you're looking for.