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.
This advice matches the limited research I did on the google search I previously mentioned. Evidently, when the sync gets out of whack IE. too many contacts to change at one time it gives this message. Perhaps a way of keeping you from accidentally deleting contacts, or just poor programming code, I don't know, didn't dig that deep.
I would follow his advice as one method. I also read the other method mentioned of backing up, deleting and then restoring the contacts through sync. Point is, as I understand it, your phone and whatever account you are synced to are grossly "out of sync" and this the reason for the message you keep getting. Another solution I read was to turn sync off! Not sure if that is the best advice but it would confirm if sync is causing the message. If not sure which account is at fault, I would step slowly, research, and back up my contacts before deleting anything. Hope this helps.