I do not know if your case will be the same as mine, I also have that model and initially also brought me crazy thing storing contacts.
When you create a contact you go three options: Save it in your phone, sim or google. The only contacts that you synchronize (or at least I came to that conclusion after extensive testing) are those who have stored in the latter.
Maybe that's the problem, you want to synchronize you have stored on the phone (that's what happened to me). If this is the case I know of no faster way to change all the contacts, I had to change them one by one, but I recommend that if you do this you do online and then sync "reverse" (pass Internet mobile).