I've spent hours on the phone trying to figure it out, no luck. They sent me to the store. The store said they couldn't do anything, call technical support. It seems to be an issue they know about, but don't have an answer for. That's why I came here, hoping to find some help.
Make sure your contacts are saved to the phone and not just google gmail. I had this trouble recently as well, between getting my contacts from Microsoft Outlook, to gmail, to the phone so I could use the back up assistant. Do a search on this forum for contacts and you can find the solutions to correct the issue (hopefully)