In order to cal a test system, you may need a relatively well-cal'd tester to start with.
In one case of trying to cal a system, I was getting consistent cal verification failures for the Source 4 Relay test in the Cal Test Exec. But, when I recal'd starting from the backup of the tester (the last know good cal of the tester), the cals worked fine.
I believe that verification is run after the calibration and if it fails it means that the calibration just perfromed was faulty. What you saw, to me, would indincate that the old calibration was still good, but that the new one was bad. A failed verification should indicate a bad cal. It does appear that in some cases a cal can get so bad that it requires multiple re-cals to correct (or maybe an independent calibration reset).