Well... so much for my "Solved" claim.
After reading your reply and then running a test I am right back where I left off with any contact added from SMS or Recents not showing up in Contacts.
It did in fact work as described, but I ran the test only before syncing contacts with iCloud. It's iCloud that's screwing this whole thing up.
Grrrr...
Here's what I've discovered upon further investigation.
If, under Settings > General > iCloud, I turn iCloud syncing off for "Contacts", select, "Keep on My iPhone" and then add a contact from SMS / Recents, the contact shows up under the general "Contacts".
As soon as I switch iCloud "Contacts" syncing back on, the newly added contact disappears from my contacts list and can only be found by doing a Spotlight Search.
Being that this is a problem that is somewhat related, but ultimately different that the problem that this was initally created under I have created a new discussion about it, which can be found here:
https://discussions.apple.com/thread/3676941
Yjsoon, it would be great it you'd chime in, there so that any insight you discover can be added to the discussion.