Hi,
I too am a big fan of low magic gaming, and I have been running the same low-magic campaign for almost 8 years, playing once a month or so (started in 2nd edition AD&D, transplanted to 3rd D&D). The PCs are about 10th level now, but it has worked well. Here are a few things I found helpful.
1) The hit point concept has to be rethought. Our solution was to lower HP so that they are size-dependent, and each PC gets a set # of hp per level considering their Con score as well. This has worked out well, the 10th level paladin as around 60 hp, as compared with 10d10+40 (avg 95 or so) in 3E. We left the spell damages the same, with a few minor alterations (I'll come to that in a minute). Creatrue hp (such as ogres and trolls) stay mostly the same as in the books, but also accounted for size. Yes, I know this makes monsters really tough, but in a low-magic gritty game, shouldn't monsters actually make even experienced PCs fearful? We also use ciritcal hits, and more recently, DNDChicks Critical Effects (which I wholeheartedly recommend).
2) We used all the base classes from the D&D PHB, but removed the ranger's spellcasting abilities, toned down the paladins abilities, and gave bards only spells that are illusions or charms. There are no sorcerers, and wizards have to find EVERY spell they have- they do not automatically get new spells when they advance a level. Priests have to learn spells too- they don't get the whole list when they go up a level. I found this also personalizes priests a lot more- priests of the same god might have focused on completely different aspects of their deity, and have different spells as a result (contemplative monks vs crusading knights).
3) Magic is much more scarce, and requires PCs to be gifted magically. When we started, we gave a base 10% chance for PCs to be able to use magic, although a feat could also be used in 3E. The biggest pain in the butt was that we had to reorder the spells levels based upon their effects in consideration of a low-magic setting. For example, any damage causing spell had its level increased by at least +1, and if it affected more than one target, its level was +2. Spells like Charm Person are much more powerful than a first level spell should be in a low magic setting, so we bumped it up too. Yeah, it was kind of a pain in the butt to do this, but it made the game more enjoyable in the long run.
Also, most magic in D&D is combat-oriented, and that makes it lose much of its subtlety. Part of it is how you role-play the spell being cast (such as several posters have said here), but magic in this kind of setting should be less combat oriented and more mythical in aspect. We made up a lot of non-combat and utility spells, including about 100 different types of curses. Also, the concept that if you do x and y, z always results in a magical spell is somewhat boring. We used casting rolls, rolling a d20 + spellcraft skill trying to beat a DC to cast a spell (10 + 2x spell level). If you roll over the DC the spell works as normal, but roll under the DC, and the spell might botch completely, go off at lower strength, or do something really odd (depending on how much lower the roll was than the DC). This makes magic a lot less predicatable, and adds back a certain element of mystery to the game.
By the way, magic is scare in my game, the PCs best weapon is a blessed sword that is +2, but once per day can cause all withing 30' to cease hostile activites for as long as the user does not initiate a hostile action, or one hour passes (Will save to negate). No major magic items, relics, etc. The PCs each have one or two minor magic weapons by now, but all of them have some small cool ability like this- after all, in a low magic world, no one in their right mind is going to make a simple +1 weapon with no other qualities.
4) Since magic is less common, there needs to be a way for PCs to heal. Our answer was making up a list of 200+ herbs that do anything from curing damage, to acting as decongestants, strength enhancers, etc. While herbs take longer to work than sure spells (overnight at least as compared to instantly), this has added a whole new aspect to the game too- characters spend time trying to find fabled herbs for their mecidinal (and mystical) effects.
5) Clerics use a system where they are awarded the ability to cast higher-level prayers by demonstrating devotion to their deity (no I don't mean just killing things). Clerics gain something called faith points, which lets clerics access spells equal to their faith point total. Faith points are given out by the DM for acts the PC does, usually in .1 to .3 increments. So a cleric with 3 faith points might be 10th level, but still only able to access 3rd level spells. We found it really helps the players of any religious character put the goals of their faith first, because there is some tangible reward for it now.
Those are the major changes I can think of that I have made over the years. I am sure I am missing lots of little things, but I hope this has helped. Hopefully this can spark some new discussion. Oh, and if you do start a conversion, I'd be happy to help as well.