Looks like I was using the wrong URI. Also I switched to a "new" way of modifying the table:
ArrayList<ContentProviderOperation> ops =
new ArrayList<ContentProviderOperation>();
ops.add(ContentProviderOperation.newDelete(Data.CONTENT_URI)
.withSelection(Data._ID + "=?", new String[]{i})
.build());
getContentResolver().applyBatch(ContactsContract.AUTHORITY, ops);