Complexity is bad. What is good is having interesting decisions to make. Complexity is just the cost to having those interesting decisions. So people confuse complexity with the interesting decisions themselves. But complexity isn't the interesting decisions; complexity is bad. Complexity requires more time and effort to implement, iterate, and tweak on the part of the developers. If there are two systems that offer the same richness of interesting decisions, the simpler one is the better designed one. When designing something a designer should always strive to find ways to make it simpler without reducing the quality and quantity of interesting decisions. This is what elegance is. It is easy to add increasingly complex mechanics to try and abstract something or provide choices. It doesn't take a skilled designer to do that and it will usually decrease the quality of the decisions available because it will be easier to break and the developers will have less time and resources to implement, polish, and iterate each component of the system. The KISS principle doesn't magically stop applying when designing video games.
All of you people who think complexity itself is good, which apparently includes a butthurt mod who changed the title of this thread(very professional BTW), are wrong and have a poor understanding of game design. When you are designing a system you are constantly trying to find the best balance for the system between providing a richness of interesting decisions and complexity. Trying to maximize the richness of your interesting decisions and minimize your complexity. People who understand what they are doing when designing systems anyway. I suppose there are people who confuse having a more complex system for having a better one with more interesting decisions. They always reveal themselves when this topic comes up.
It is also worth noting that interesting decisions aren't the only factor one is considering when determining the entertainment value of a game. There are many other things to consider including what kind of experience it provides. That is also an important factor the systems designed for the game should support and reinforce that experience.
You're absolutely right it's about interesting decisions. I am completely with you on that. Yet this is tricky. You say it's not tricky, but I think it's. The fact it's tricky is why so many games have small audiences.
1. Complexity gets confused with depth.
Complexity is different from depth in that it "pulls you out of the game." It causes you to stop using your intuition/experience and causes you to read manuals or descriptions or pour over technical details. It's a far less natural thing to do and this is why it pulls you out of the game and will make it less accessible.
JA2, for example, is a game some people hate and some people love. It's a good one for me to pull out because it's so blurry. Is it complex or deep? It's easy to spin it one way or the other, depending on the person.
One of the things which may have been too complex were how you had to press keys to highlight the line-of-sight. This gave you three color codes for tiles: barely visible, moderate visible, fully visible. Using this information, you could judge how clean the shot is for your characters and your enemies. It was pivotal information and you HAVE to use it on higher difficulty. One deficiency was you couldn't judge what the line-of-sight was at a position not occupied by one of your party members, yet it's probable the enemies can. And I think this line-of-sight "feature" did pull you out of the game and that's not usually a good thing.
2. It's too hard or just not fun! It's too inaccessible!
I love racing games. Those're usually very intuitive. At no point do you need to read a description or read a manual or otherwise be "pulled out of it." However, sometimes they have power-sliding. Power-sliding, traditionally, has been a simulation-esque feature. Many gamers perceive it as inaccessible. It used to be a common sight, until it became an option and then was totally absent in some. I tend to prefer power-sliding. I don't think power sliding is about depth or complexity, but it's a very tight and uncompromising feature which some, paradoxically, enjoy.
Or what about a game which is primarily action-oriented having too many puzzles? Players who're accustomed to action will not want the puzzles. For them, the puzzles will make the game incaccessible. So they'll have to be removed.
Note that these things aren't strictly complex or deep. They're just unwanted or unnecessary, given the audience. Placed in the wrong game they can be interpreted as bad. You don't put power-sliding, for example, in a racing game which is focused on arcade gameplay. You AT LEAST make it an option.
___________
I think game makers will continue to confuse depth and complexity, even if it's avoidable. I also think some games will necessarily be harder to play for some or just not fun for them, but this doesn't mean they're too complex or bad games.