Yes, i would almost certainly say it's because they start with a horse breeder in the high period, as they seem to do perfectly well starting with nothing in the early period. The upgrade path is very sensitive to major changes and some changes can result in the AI getting stuck.

VI is a prime example where actually the native setup is not conducive to smooth AI play. All the provinces with +1 unit bonuses that contain NO starting improvements, i.e. all provinces bar the capitals, will get stuck and the AI will never build the bonus units

Actually your upgrade path looks good and is probably slightly better than the one i suggested, although i'd have to see whether it was compatible in the early period in provinces starting with nothing.

Let me know how you get along.