Judging from the OP's report: "Delete all contacts" deletes contacts that have never been synced onto the phone.