I think perhaps one of the best things a DM can do to create a low-magic setting that is well-balanced and believable is to pick one type of magic from the myriad of options in D&D and state that this is how magic works in the world. Most fantasy novels (or films, etc) don't have the obscene number of wildly different types of magic that D&D has.
Choose one of the three types of magic from the Tome of Magic, for example, perhaps expand on it a bit, and tell the players that this is how magic works in the world. I'm not really that familiar with the types of magic in ToM -- essentially because no matter how interesting or flavourful they are, there are already too many different magic systems in D&D -- but if Binding or Truename magic is the only magic in the world then it seems like a lot of the flashier effects aren't going to be possible. There may be greater costs to a magic-using PC. And if you're not having to juggle prepared arcane magic, spontaneous arcane magic, prepared divine magic, spontaneous divine magic, psionics, incarnum (who uses it anyway), the Shadow Weave, wild magic, Warlock invocations, etc. When it's all thrown together, the magic really loses a lot of its flavour and becomes this bland mishmash of vaguely-related magical powers.
Of course, it is my opinion that a D&D campaign works the best (from the point of view of world believability and flavour) when a DM selects a subset of the game to include in the campaign. No game world really needs several dozen sentient humanoid species. If a DM really likes Incarnum, then it probably works best if that is how magic works in the world. Does the game really need both the Sorcerer and the Warlock, which are two different approaches to what is essentially the same concept? Options for character creation are fantastic, but it's really difficult to evoke any sort of strong flavour -- low-magic or otherwise -- if you're assuming that everything published in every D&D books exists in the world. Even just the contents of the first Monster Manual, taken as a whole, leaves me with that bland mish-mash feeling.
So my best suggestion is just to pick the elements of D&D that best fit the low-magic feel that you are going for and decide that the rest of it doesn't exist in the world. You don't really need to change too many rules if you're just omitting certain classes, monsters, spells, or items from the game.
If I want to create a believable low-magic game, I might do the following:
Character Options
- replace the PHB Ranger with the Scout from Complete Adventurer. They fill very similar roles in the party and the Scout drops all of the druidic magic
- Clerics are not simply priests who staff the local temple. To be a Cleric is considered both a blessing and a curse. The Cleric is born with an intrinsic connection to the divine and will usually be guided (directly or indirectly) to his or her destiny. To wield the powers of the divine is an exceeding rare and special privilege, but it is also a responsibility. Clerics are trained in the art of combat (good BAB, heavy armour proficiency, d8 hit die) because they are the agents of the divine in the mortal world, and it is their calling to venture out into the world to defend the followers of their faith and perform epic deeds in the name of their faith.
They may be dedicated to specific gods if that's what floats your boat, but I prefer the more detatched deities that nobody can really say whether or not they exist. Clerics serve a divine cause, whether it be individual gods, a pantheon, or a divine principle. The devoted faithful who staff the churches are just normal, non-magic-wielding humans. If there is a god of war or battle, then the vast majority of followers in his temple are going to be Fighters or Warriors.
- Druids don't really fit into this cultural view of religion as well, so there are no Druids in this world. Or perhaps they are the very rare individuals destined to serve the divinity inherent in nature.
- to be a Paladin is not only a calling, but is also something that one must strive for. Replace the Paladin with a prestige class, either like the Paladin PrC in Unearthed Arcana, or else the Holy Liberator PrC.
- the Bard could be eliminated fairly easily, if you want to get rid of all of the minor spellcasting base classes and leave spellcasting totally the domain of Clerics and Wizards. Or if you like the idea of the magic of song but don't want a spellcasting Bard, Monte Cook's variant Bard from The Book of Eldrich Might II has the ability to use spellsongs that is more flavourful but more restrictive than just casting PHB spells.
- the Monk and all of its pseudo-magical powers will probably not be missed by many, and can easily be dismissed as not culturally appropriate.
- the study of magic can only be undertaken by those who possess an inborn ability to control the arcane energies. This doesn't restrict PC Wizards, but is a story-based way to limit the number of NPC spellcasters. In addition, the study of magic requires many, many years of study and practice under the guidance of an experienced Wizard. A PC can start out his or her career as a Wizard at 1st level, perhaps a bit older than the 15-19 years of age given in the PHB. But unless a PC wants to take 10 years of game time off, he or she cannot take levels of Wizard unless that was his or her class at 1st level. Perhaps waive this restriction for Elves, to suit the flavour of the race, although you may want to drop one of their other abilities.
Wizards will not gain free spells known at each level -- they have to be researched. And Wizard players have to keep track of material components and not just buy a pouch of spell components that is assumed to contain any needed components of 1gp or less in cost. And some of these components may be hard to obtain. If arcane magic requires both an inborn talent and long years of study, you can drop the Sorcerer class as it is not needed.
- weapons and armour of +1 and +2 bonuses are due to craftsmanship and quality of materials, not magic. To enchant a weapon, it must be at least a +3, which sets the costs high enough that there's not going to be that many of them. And instead of trading in a +3 weapon for a +4 one, there are rituals and rare magical components that allow a PC to enhance his or her weapon. Or perhaps they just need to spend XP to improve the weapon, as the bond between the PC and his or her magic weapon grows.
- if PCs don't have the "assumed" stat-enhancing items at a given level, or have lower-plus weapons or armour, then you can assume that as they hit mid-levels they will need to face slightly lower CR encounters than they would normally.
Well, I need to get back to work, but that's how I might start building a low-magic campaign that doesn't really change the existing rules too much -- it leaves out aspects that I don't think fit, but changes as little of what it uses as possible.