Canis said:
Leadership is a good route for Charismatic generals to build a power base with, but I really think it applies more to personal loyalty than to an army which is paid by and is loyal to the king, but is simply commanded by a general.
If we're talking a psuedo-medieval world, I'll point out that almost all generals were "Charismatic" in the sense you mean. During that time period, armies were loyal to both general and king; this is why you had so many kings leading armies - it was risky otherwise.
Something else to consider - in medieval times, the largest "typical" unit was something roughly the size of a modern platoon (or Roman century). The leader was called a captain. True generals were very rare.
Also, even in professional armies (like Rome's or the modern miltary), Charisma plays a HUGE issue in who becomes a leader of troops. In the modern US army, there is a point where politics (ie. Charisma) becomes almost even more important than competence. That point resides roughly at the transition point between Colonel and General. The other US military branches have similar points.
In fact,
\<invocation of Board Guru\>
I CALL UPON THE GREAT *SHARK*!
\</invocation\>
I'll submit that in terms of "general-ship" the Leadership feat is probably more important than any other factor.
Also, medieval nobles were NOT the educated class - that was the clergy. Many, many, nobles were unable to read or write. I'll grant that there were more educated nobles than serfs, but that isn't saying an awful lot.