The reason they take so long to train is that they lose up to three skill points when they fail, I think they lost all the traits they've gained, but retinue stays. Still, I managed to eliminate the Greeks and Dacians via assasination when they were down to two provinces each.