Per the comments, you're doing it wrong.
You can't simply change a layer's CRS if it was defined as another.
How to resolve: Make sure your layer in the original EPSG:2193 CRS.
If after you load the basemap, the canvas doesn't change to EPSG:3857, change the canvas to EPSG:3857, and zoom to your layer's location in New Zealand.
You mentioned in the comments that updating to the new version of QGIS solved the problem. I assume you updated from a 2.x version to a 3.x version.
The solution to your original problem would have been to turn on "on-the-fly reprojection." This feature allows multiple layers in different CRS to be displayed as if they were all in the same CRS without creating a new version of each layer.
In the QGIS 2.x series, on-the-fly reprojection was an option that could be toggled in the project properties. In QGIS 3.0 and later, on-the-fly reprojection is always on. That's why updating to the new version of QGIS solved your issue.