Hi
I had a similar problem, but I managed to solve it.
I saved the contact but then couldn't find it in search results. Typing the number showed me it in a Dialer, but not in search results. It was there somewhere, but wouldn't show.
Then I looked closer and found that when I found it in Dialer, I was able to dial the number. After dialling, I went to Call Log, and did Edit Contact from there.
I discovered that this contact, in the Groups section, just under Surname, was in the Default.
All my other contacts, imported from an old handset, were assigned to
My Contacts in the Groups section.
Therefore, I changed the one which I couldn't see in the search, in the
Groups section from Default to My Contacts, and now the contact shows up in search results.
Conclusion: When adding New Contact, always change in the Groups option from Default to My Contacts (or any other group), so it is not left not - assigned (Default) and shows up properly. Android seems to require you to make a decision in the Groups option, rather than leaving it unchanged (Default).
Hope it helps.