I think that Soren Johnson mis-phrased his title for the complexity paragraph... he's not really talking about complexity it seems in terms of game design and layers, but of the number of individual pieces of content within existing layers. Like is a swordsman unit really required when you have the axeman as currently implemented? Some would argue yes, some would argue no, but this is the sort of question that illustrates what he meant, at least it seems so to me.
But for the sake of the arguement, I think the success of a more complex design is almost entirely based on its implementation. For example, look at Dungeon Siege 1: The character leveling system was too simple, by far. It's important to keep in mind there is a such thing as too simple. Now look at Dungeon Siege 2: Here you had the same basic system with a new game element (skills) that added complexity and added to the game in a positive way. Titan Quest functioned similarly but was even more complex and polished, in fact, Titan Quest had the best character development system of any hack-n-slash rpg i have ever played, but the game's short campaign was less-than stellar and had ZERO replay value.
Now look at Oblivion's character development system: Its basically the same as Dungeon Siege 1 at its core. Dungeon Siege 1 had one of the worst systems because of its pitifully simple design, but Oblivion's tops even DS1 and its much much more complex. The difference is in the implementation: DS1 -> DS2 saw a new layer that really added to the capabilities of you character and made sense within itself. DS1 -> Oblivion saw basically an increase in the components of the same useless layers and new layers that added nearly nothing to the experience. The result was a mess that failed to be enjoyable. And no I'm not implying Oblivion was made by the same company or was a sequel of any sort to Dungeon Siege, just the similarities of the character development systems present within them.
The golden rule is responsiveness. If you can implement an additional layer of complexity but keep the overall system responsive and meaningful, you will probably add to the game in a positive way, but just like there is a such thing as too simple, there is also a too complex.