The Leadership feat (and, by extension, the Thrallherd prestige class, which is effectively "Leadership but better") is commonly recognized as potentially game-breakingly powerful. The common response is to just ban them, and perhaps that's a sensible response. I've never encountered any players who wanted to go to the trouble of figuring out how Leadership works just for its own sake; the only reason most people want to take it is to abuse it. "Has minions" is certainly a fun character archetype, but D&D makes it awkward enough to make it undesirable.
But it's never fun to take away options. So what can we do to fix it?
Well, the first two questions which spring to mind: what, exactly, is the problem with Leadership (and by extension with Thrallherd)? Does Thrallherd add any extra problems on top of that?
I don't know what most people use their Followers for, but they're not likely to be of much use for anything other than setting them up in a city running a business and funneling most of their profits to you, and if you want to take a feat to get a little bit of the pittance that NPCs can earn in a lifetime, that's fine. So the followers are not a problem.
While I'm on the topic of followers, I'll answer the second question before returning to the first. The main difference between the thrallherd and the Leadership feat is that the thrallherd can abuse his believers mercilessly with no penalty, while the leader takes a penalty to his leadership score if he does so. So the thrallherd can potentially have, for example, an infinite number of human sacrifices.
Solution: if that many people are going missing, the authorities are going to start investigating. Paladins and celestials are going to start coming after you, in large enough numbers as to constitute a genuine inconvenience.
So, having dispensed with any problems inherent to followers/believers, the main problem with Leadership the cohort. Specifically, that the cohort is effectively an extra PC (a couple levels lower than the others, but who doesn't take experience away from the party).
We can fix that by obeying the rules laid out on pp. 105-106 of the Dungeon Master's Guide. Specifically, two things: first, the player can attempt to attract a cohort of a particular race, class, and alignment, with no guarantee that this attempt succeeds; second, the PC can control his cohort's actions in combat, but the DM controls all the specifics of the build. So if the PC tries to attract a gray elf batman wizard, the DM is entirely free to hand him a goblin commoner instead.
So the problem is satisfactorily solved. Done. I would, however, like to consider actual modifications to the rules, for those who aren't satisfied with the above easy solutions, or for DMs who don't want to go to the effort of building cohorts and punishing Charles Manson PCs in-character.
To wit: limit the classes. Followers and believers can only ever be NPC classes (or, far better but slightly messier, tier 6 classes). Cohorts and thralls start as NPC classes (or tier 6 classes, or maybe let them take tier 5 classes), but you can take additional feats to improve the list of classes they can take.
Without the following feats, cohorts and thralls are limited to Samurai (Complete Warrior), Aristocrat, Warrior, or Commoner. Followers and believers are always limited to those four classes.
Improved Cohort I
Prerequisite: Leadership and character level 8; or thrallherd level 2
Benefit: Your cohort or thrall may take levels in Fighter, Monk, Ninja, Healer, Swashbuckler, Soulknife, Samurai (Oriental Adventures) Expert, Paladin, or Knight.
Improved Cohort II
Prerequisite: Improved Cohort I; and character level 10 or thrallherd level 4
Benefit: Your cohort or thrall may take levels in Rogue, Barbarian, Warlock, Warmage, Scout, Ranger, Hexblade, Adept, or Marshal.
Improved Cohort III
Prerequisite: Improved Cohort I-II; and character level 12 or thrallherd level 6
Benefit: Your cohort or thrall may take levels in Beguiler, Dread Necromancer, Crusader, Bard, Swordsage, Duskblade, Factotum, Warblade, or Psionic Warrior.
Improved Cohort IV
Prerequisite: Improved Cohort I-III; and character level 14 or thrallherd level 8
Benefit: Your cohort or thrall may take levels in Sorcerer, Favored Soul, or Psion.
Improved Cohort V
Prerequisite: Improved Cohort I-IV; and character level 16 or thrallherd level 10
Benefit: Your cohort or thrall may take levels in Wizard, Cleric, Druid, Archivist, or Artificer.