I've seen that message before. Happens when I delete all my contacts on the phone and then sync to Google so that they get deleted there as well. (I do this prior to FDR and backing my current contacts to v card so I don't get duplicates). To solve it I delete no more than 5 contacts at a time, sync to Google, delete 5 more, sync to Google, etc. Try this and post back with a response to let is know if it worked.