As several people have already pointed out, many people play RPGs precisely because of the complexity, not despite it. In fact, that's probably at least part of the appeal for the vast majority of players. The game gives them something to learn and master; trying different options and exploring ways (ways that are not immediately obvious) to better one's character gives the game an extra dimension of challenge that isn't really offered elsewhere.
Exactly.
In fact, in Basic Game focus groups (lo those many years ago) we saw over and over again that if kids couldn't find a rule they needed, their games simply stalled; the "you're the GM; make it up" or "it doesn't really matter, move on" thoughts were not on their radar screens.
This goes to my other point. That rules are for GMs, and your typical GM - especially a new GM - needs and wants alot of them. It's burdensome to invent rules. Many otherwise good GMs can't do it. The real interface of the rules in the game for a group in a new game is this:
1) Player makes a proposition.
2) GM applies a rule, perhaps without even telling players what the rule is.
3) GM tells the player what the outcome of the proposition is.
The point of the rules is to make it easier for the GM to get through step #2, and sometimes that alot easier in a rules heavy system than it is in a rules light system. In particular, a rules heavy system is almost essential to providing answers to proposition where the player wants to quantify something - not simply get yes/no, pass/fail. How much can I lift? How far can I run before I get tired? How long does it take me to make a dugout canoe using stone tools? How long does it take to tunnel through the wall? If those questions aren't specifically addressed in the rules, then its a potential failure point in the game. It's at that point that system finally starts to matter, because a system that consistantly gives poor answers (or no answers!) to questions like that in the hands of a new GM will frustrate everyone. Now, of course, if the GM can handle all of that by fiat, then system still doesn't matter but the game only works in the hands of a narrower and narrower set of GMs with a rarer and rarer set of skills.
The sort of person that becomes a GM is typically a rules freak. Some players are rules freaks, and we call them power gamers, rules lawyers, and so forth. And that's ok. I think we are typically way to snobbish in our dismisal of players that love RPGs because they love exploring system mastery. Those players can be a problem it's true, but so can any kind of player - casual gamers can be too casual, RPers can put character ahead of game, goofs can be goofy to the point of disfunctionality, tactical minded players can become domineering table sergants that want to play every other players character for them. But the important point is that new players are't really ever turned on or off by the complexity of the system or really anything having to do with the system, because that's not how the new player plays the game. I've played several systems that I never even learned the rules to. I didn't need to know the rules. I once played a couple sessions of D&D with a DM that didn't even let the players see their own character sheets. You don't even need a character sheet to play an RPG! The new player doesn't interface with a sytem; he interfaces with the GM. How frustrating it is to interface with the GM, and how much reward he or she recieves for doing so is the real determining factor.
Their are several real problems with 4e as far as attracting new players goes, but its nothing to do with complexity. Nor for that matter are any of the problems so great that its going to prevent 4e from attracting new players (because system doesn't matter!). One problem I see with 4e from the standpoint of starting up new tables is that it is a player focused rules set when players per se aren't what a game system should try to be attracting. A rules set should be aimed at GMs because its the number of GMs running your system that determines its success. There are a surplus of players in the world and a shortage of GMs. Any GM with decent skills can attract more players than he's capable of handling. There are millions of lapsed players out there wishing they knew a decent GM.
Which is for example why WotC was always making a huge mistake trying to be the 'rules company' while outsourcing all the adventures to third parties because 'they didn't make money'. Silly WotC, all the money is in the modules; the system doesn't matter. The suits at WotC probably think the problem right now is the OGL because they are focused on 'system' as what makes an RPG successful. The real problem is that they don't understand what grows a market for RPGs because they don't know who their customers are or how to make new ones. they still don't know which is evidenced by the essentials and introductory lines that they are coming out with that offer nothing to GMs.
Nothing in the past few years has told me 4e D&D is doomed quite like the number of players I've talked to locally who say things like, "I prefer the 4e system, but the campaign I'm enjoying most right now is a 3.X/Pathfinder game
because the DM is better."