What could cause fluorescent lights to sporadically not come on?
Fluorescent fixtures can be rather tricky. With that many installed on the same circuit, what you might be seeing is an unbalanced load on the circuit, causing some of the fixtures to have full current and others, less, and quite simply a ballast, or any fluorescent will not work without full current. With the warm up times of older ballasts,  combined with different features of newer electronic ballasts, this could be the answer.

Isolating part of the fixtures on the circuit from each other quite possibly will solve this. The simplest way would be to install two (or more) switches instead of one, preferably running from different circuits. 

You might also consider replacing some, or all, of the can lights with LED. This would considerably lower the load, as well as saving energy. Quite interesting that you have can lights with an external ballast, as well. I've never seen that. What type of bulb do these use if not a CFL? Is it possible that what you think is a ballast is simply a wiring box where the can lights connect to the wiring, or some sort of dimmer control?