It's complex, but not overly so. I've spent twenty-plus years playing and GMing the Hero System, which is often held up as the poster child for complex game systems. It's just a different skill set to master.
But therein can lie the difficulty.
On the surface, d20 has a very simple core mechanic. So does the Hero System. So does WW's Storyteller 2.0 (used in Exalted) for instance. But as a Hero veteran, D&D (and ST) vex me because both are exception-based rules systems.
With Hero, if you want a particular effect, you purchase it with points. Whether you're creating an elf's low-light sight, a mage's spell to draw life from his enemies, or a warrior's magic sword, mechanically the process to create these effects is the same, and no matter how convoluted the computations might be to figure out the point cost of the effect, the mechanics and the inter-relationships of the various effect never change, no matter how deeply down you drill.
As a result, even though the game is complex, and there are a myriad number of ways to accomplish various tasks, it's reasonably easy for a GM to keep things balanced once he understands a few basic principles and how they inter-relate. It's not perfect or flawless, and I don't want to paint it as such. But the consistency goes a long way to making it simple.
With an exception-based game, you don't have a consistent means of constructing effects. In the case of D&D, you have hundreds of Feats, each of which allow the character an exception to the standard rules in some greater or smaller way (ditto for Exalted's charms). I've heard more than one person describe this as being similar to the underlying design philosophy of most CCGs, but having never gotten into that end of the hobby, I really can't comment on it; it's not new in RPGs, by any means, just brought to a whole new level with D&D.
With an exception-based games, the inter-relation of the exceptions almost becomes a game within itself. Each new Feat is a potential game-breaker and must be viewed in terms of Feats it might make more or less attractive, and the ultimate impact it could have on the game. With so many Feats, so many factors to examine, the potential for things to break down is significantly higher.
Which is not to say that a game like the Hero System is free from game-breaking effects. I do, however, think they're easier to catch because of the design philosophy of the game.
So, for the purposes of the GMing firm of Me, Myself, and I, D&D is overly complex, because I find extensive exception-based rules systems require me to juggle too many factors as a GM. As a player, all I have to do is worry about my own character, so it's not nearly such a big deal. But GMing is what I mainly do.