If you use Google Keyboard you might find that the the sync is greyed out under Languages & Keyboard - Google Keyboard - Accounts & Privacy. To fix this you need to go one page back and click on Text Correction and scroll down and make sure Suggest Contact Names is on. Go back to Accounts and Privacy and sync should be turned on.