To make it work for me I had to let all the updates complete after "factory resetting" the phone.
After all the updates were completed I added Google email and contacts and finally they synced.
*I have used reset to factory settings multiple times to get the Contacts to sync.