I like to think of elegance in rules as similar to elegance in the design of a mechanical watch. Every piece has its place, every piece does exactly what it should do, and the whole functions perfectly.
Elegance has nothing to do with how many rules are in a game. What matters is how well those rules work together, and how well they work with the end user. It would be foolish to say that watch A is more elegant than watch B simply because it has fewer parts.
For example, there are lots and lots of feats in D&D, but the concept of a feat (an exceptions based rule attached to a character) is elegant. If you play a wizard, you never need to understand how Cleave works. Even the DM doesn't need to understand it, unless a monster has it. Cleave is a wonderfully elegant feat, because it's so simple yet so powerful: Once per round if you drop an opponent, you make another attack. Those 12 words cover the entire sum of the feat, and it has an exciting, important impact on the game.
In contrast, an inelegant feat is complex, slow, and uninteresting. Imagine if Cleave altered your attack bonus or did other weird things to how you attacked. It would slow down the game to dubious benefit.
Problems arise in D&D when various exceptions based elements mesh poorly, or when one system collides with another. The advancement rules for BAB are very elegant when taken on their own, but they fall down when, say, the rogue can't possibly hit a monster, but the fighter hits it every round. BAB progressions are easy to remember, but if the gap between them becomes too large it's hard to find a sweet spot for monster ACs.
By the same token, simple does not mean elegant. Call of Cthulhu has very simple mechanics. If you roll your skill or less on d100, you succeed. Yet, it falls down as soon as you try to add difficulty factors, opposed checks, and specific skills into the mix. Dodge leaps to mind - my ability to avoid your attack has nothing to do with your skill. If I have a maxed out Dodge skill, even Great Cthulhu can't touch me!
Another aspect of elegance lies in "spending" complexity in the right place. Complexity in stuff you do away from the table - leveling up a PC, designing a new monster, is fine (within reasonable limits), since it has no impact on how quickly the game moves. In comparison, the rules for climbing a wall are best kept as simple as possible. Climbing doesn't come up all that often, and when it does we generally just want to climb the wall and get it done with. Same thing with grappling, casting a spell while underwater, swimming, and so forth.
In other cases, rules should be simple because we can expect players and DMs to use them a lot. If every attack roll required a table look-up, the game would slow dramatically.
There are some places were complexity is a good thing. I might have a system for resolving a battle between two armies with a few die rolls. Complexity here might be a really good thing. The players want the chance to do stuff to alter the battle. Tactics should have a role in who wins. A skilled commander should have an advantage over an inept leader. If it takes 10 minutes of game time for the DM to describe the battle, factor in the various modifiers, make several die rolls, then declare a winner, that might be exactly what the game needs.
On the other hand, taking 10 minutes to resolve a Climb check, or to work out a single character's grapple action, is probably not so good.
Handling time is a big part of improving D&D. If a fight takes less time but is just as fun and interesting, the game is simply better. You have more time for roleplay, story, and other fights. Players spend less time watching each other or the DM take actions. The game moves faster, and you get more stuff done in a session.
So to me, all that stuff ties into my definition of elegance. As a designer and developer, my goal is to translate as many seconds of gaming as possible into fun seconds. I think of D&D as a machine that you feed your free time into. Some percentage of that free time becomes fun. I want that percentage to hit 100.