I've never really liked the feat. In reality, should you look to the middle ages the 'leaders' often would have been considered lower in level compared to their 'followers'. The only exception I can think of would be the PHB2 idea of Affiliations - where the head of the Affiliation is not necessarily a higher level than those a level or three below him. He just happens to have better connection or to have been involved in situations more useful to the affiliation than those of higher level who are a part of it.
The closest 'Leadership' - as a feat - comes to this is if the character is a 'leader' of a mercenary band, a pastor of a church (or bishop of a cathedral / diocese), or a leader of the band (in the case of a group of bards or other entertainers), etc. In each instance the group is composed of similar 'classes' (or conceptual classes - such as fighters, warriors, etc working together in a mercenary band).
The Leadership feat does not limit the group to such, despite the fact that - as I understand it - it is meant to substitute for the fact that in a prior edition the fighter (and some other classes?) would automatically attract a band of lower level cohorts, combatives, etc under his command upon reaching a certain level - and the band would grow automatically with his increased level. This is much the same as with Weapon Focus and Weapon Specialization; they were automatic for the fighter upon a certain level in a prior edition but are feats in the current edition.
As it stands, the feat is in some respects flawed, in my opinion. Even the cohort - the highest level addition - is notably less likely to survive in a typical encounter. All those beneath him are mere fodder if they are brought along at all. In all honesty, I cannot imagine how this could have worked in prior editions. How did the followers survive? Did they have other rolls, and if so, what? Do those roles no longer exist in the current edition?
I'm of the opinion that a character should not have to have a feat for Leadership - or for owning land (the Landlord feat from the Stronghold Builder's Guide), etc. Instead, I tend to think that such gains should be determined by the DM. A dozen followers of 6-10 levels lower than than the PCs should not require a feat. Receiving a title or land-grant similarly should not require expending a feat.
Instead, perhaps the PCs could have two pools of wealth, one more symbolic than the second. The primary one would be for the requisite magic items, etc, while the second and more symbolic one would be used for dealing with more basic considerations - such as paying a cohort, upkeep for a keep, buying a ship (or even just passage on a ship), etc.
Actually, perhaps - since this second one is merely symbolic - it could be reduced the the Wealth check used in d20 modern. As they increase in level they gain a bonus to this - which in turn is used to determine whether the party (or a member of the party) can buy that boat, bribe that guard, pay that cohort, upkeep their keep, influence that noble, gain that patronage, etc. It could be interesting to add a Wealth check to the game that cannot be used to buy equipment - only for non-equipment usages (such as prior examples). This would prevent the oddity of a high level group traveling around with several kings' ransoms strapped to their body but not necessarily able to buy a ship or keep a keep - at least not without losing some of the wealth they need to remain par for their level (in terms of ability to survive level appropriate encounters).