Radiosonde and other fixed climate networks are critical sources of climate change information, but measurement bias changes and uneven sampling can corrupt results. Here, simulated multi-station datasets are used to test several methods for removing step changes in bias (``change points''). Benchmark methods that remove artifacts first and then calculate trends proved unable to correct deficiencies without also removing desired signal. This problem worsened considerably when change-point times were not known a priori, leading to near-total failure in these (idealized) tests even when detected change points were held to nominally strict significance requirements. The results indicate that previous radiosonde homogenization efforts may have significantly underestimated the net impact of artifacts on trends.A new approach is proposed and tested in which trends and change-points are estimated simultaneously. This is accomplished here for the difficult case of incomplete data by an adaptation of the ``Iterative Universal Kriging'' method of Sherwood (2000b), which converges to maximum-likelihood parameters by iterative imputation of missing values. With careful implementation this method produces trend estimates whose biases are zero when change-point times are known and small when they are unknown. Random errors are also reduced. Though detection is somewhat better, the method's main advantage lies not in the avoidance of false detections---which may be inevitable in difficult settings---but in superior resistance to their dileterious effects on the climate signal.