unfortunately, your contacts store is the same as your messages store: tracker. there might be a way to specifically nuke just the contacts, but I never remembered it if there is.

if you're comfortable losing a *lot* of data (messages, etc) and forcing reindexing of all media on your phone, which will be slow for a while - then you can run tracker-control -rs, but this may have unforseen consequences. I don't recommend this except as a last resort before a reflash.