You need to add both at the same time. Otherwise, the system does not regenerates automatically the variants. In that case, you need to delete the variants of the product, delete the characteristics, save the product and add the characteristics back and the system will regenerate automatically all the variants of your product.