Welcome to Android Central! Are you entering this contact manually into your Contacts app? If so, which account is it going to? Your Google account, or the local Phone account? Make sure it's your Google account.
Apart from thesuggestion above also check the obvious. Did you enter the person's name with weird/incorrect spelling? This happened to me. I kept thinking I lost a number, but what was happening to me was the person's name was spelled as "Alayna", but when i search for it I always type "Alaina".