I saved a contact. Verified it that it is in the contacts by going into contacts and searching for the contact. Now it is not showing. It has happened twice.
Have you tried adding the contact to your contacts list through the Gmail desktop site?
This probably won't actually fix the problem (which seems to be adding contacts on your phone), but it will at least tell you if it's a phone/contact apps issue or not.