I have Googled this and haven't found any one else having this problem so I wanted to check in this forum and see if something's got messed up on my phone/account.
When I add a contact from the phone, it gets synced up to Google - but not to the "My Contacts" group. So when I search for the contact on the phone, I can't find it. But if I click on the "Other Contacts" button, it's there. If I add it to a group such as "Friends", it's in the friends group, but not in the My Contacts group. So I can't find it when I search for it. I have added the contact from received call logs or directly, but it doesn't work. I didn't have this problem with the GS3.
Can someone please add a contact from the phone and see if it makes it to the "My Contacts" group in Google?
My work around is to go to contacts.google.com, search for the contact and then move it to the My Contacts group. Really annoying and I'd like to find the fix for this.