I had the same problem. Alot of people said deleting voicemails worked, others said Google+ was the problem so they disabled it. But nothing worked for me so I went into:
1. Google+ App
2. Account settings
3. Clicked contacts
4. Clicked Keep contacts up to date
After this I clicked on contacts...