I encourage teaching koshinage ukemi shortly upon entry into aikido. In fact, I think it should be taught before learning rolling. Then, there's nothing scary about it.
I agree with Ellis on this statement. I learned high breakfalls simultaneously while learning rolling. I could do it competently in a few months time after starting aikido. It really depends on the dojo. There were like 30+ of us starting a few decades back and breakfalls were mandatory for 6th kyu. I've never heard of any injuries arising from this.
It's more the psychological fear of taking high ukemi that's more difficult to overcome, not the fear of risk of physical harm. Anyway, judo guys do it why not aikidoka?