when I synced my nexus to my google account it deleted all my stored contacts and replaced them with people I've never met before. the entries have their full names, their phone numbers, email addresses, places of residency and profile pics. it's pretty weird.
It has to do with iCloud. Everything I've read is basically stemming it down to that.
Trying turning it either on or off, opposite of what you have, and rebooting the phone. Also try playing and mixing it up with the Contacts button via iCloud being on or off. Have read peoples contacts coming back by doing this.
My iphone just died, randomly deleted all my contacts for the second time, so I went and restored the phone and while doing that the phone just stopped working and got the "white screen of dead".
Apparently the only way to fix it is by setting the phone to the DFU mode, but it is nearly impossible to do so since my power button is broken.