Restoring iPhone contacts from backup immediately undoes itself
It is possible that, after restore, you are syncing your iPhone with some source where the contacts have been deleted as well. If so, you will need to stop syncing and/or restore the contacts in that place as well.