I think we need to give "new players" a bit of credit here, it's not like they look at the powers on their character sheet and burst into tears at how horrible and complex it is.
Burst into tears, no, of course not. Find it overwhelming and too much like work? Definitely. Two of my four players are new to the game and both feel that 4e is too complex, primarily because of the powers. They have too many options and they find it hard to tell how certain powers differ from one another. They hate having to remember when the bard gives them 3 temporary HP or a +2 bonus on attack rolls for a single round. These two play a two-blade ranger and an Essentials slayer, which are among the more straightforward classes in 4e.
Some new players will absolutely love the way that 4e powers are set up and will take to it quickly. A lot of dedicated gamers (tabletop, video, or otherwise) thrive on mastering complex systems and enjoy spending time outside of the game sessions reading the books and learning about it. More "casual" gamers frequently don't enjoy complex systems and don't spend much time and effort (if any) outside of the gaming sessions to learn about the game.
I mean hell, have you played some of the video games out there? Some of them make 4e look like a walk in the park.
That is true, and many of those more complex games are unapproachable to those who don't make gaming their primary pasttime.
The two players in my group who don't enjoy the complexities of 4e also don't enjoy complex video games.
My wife is a good example. She is very well-read, excels at word games and puzzles, is a voracious reader of fantasy novels, has a master's degree, has a terrible habit of ripping my own logical arguments to shreds with her logical reasoning, and plays a fair number of video games. She's new to D&D and finds 4e too complex, to the point where she feels that the rules get in the way of role-playing because they require so much of her attention. The powers are the chief culprit here.
She also doesn't enjoy most modern console games. She loves RPGs and Zelda-type games that are in the vein of those that were done on the SNES. She played one session of Basic D&D after having played a few 4e sessions, and her analogy was that playing Basic D&D was like playing a Super Nintendo or DS game with a D-pad and 4 buttons (yes, it had more than that, but many games didn't use more than 4). Playing 4e was like playing an Xbox 360 game where the controller has a D-pad, two analog sticks, 8 buttons, 2 triggers, and needing to use all of those while also having to navigate a virtual 3D space and control the camera while trying to move and fight. She's finished Zelda: A Link to the Past on the SNES a number of times, yet she finds Zelda: The Wind Waker on the Gamecube -- the game which legions of gamers complained was so easy that they never even came close to dying -- to be too complicated and difficult to play.
So 4e can be fairly simple and easy for some new players to pick up -- I won't argue against that. Without getting into a debate about the scientific validity of Gardner's multiple intelligences theory (as it is a useful tool for illustrating my point), I think that 4e very much appeals to players with strong logical-mathematical abilities. From my own experience in working as a video game designer, and from interviews I've read, a large proportion of game designers (across all industries) are predominantly "logical-mathematical" in how they approach things. New players who tend to be stronger in verbal-linguistic or interpersonal abilities are probably much less likely to enjoy 4e and might find it not at all simple to learn. Yet these are quite likely the most natural story-tellers and role-players (read: "actors").
Basic D&D is a simple enough system that most anyone can learn to play in a short period of time, and then the rules fade into the background and the players can focus on all the areas that don't involve the rules. The more rules there are and the more complex those rules and their interactions are, the longer this process takes. Games with more complex rules will naturally appeal more to the "logical-mathematical" types than others, and players who don't enjoy -- or simply aren't very good at -- that mode of thinking may never reach the point where the rules just fade into the background. From their perspective, the rules just get in the way of telling a good story or portraying their characters. The gamers who thrive on mastering and tinkering with complex rules systems frequently don't understand why some other players are struggling with it.
B/X or BECMI D&D used to be the simpler game that was accessible to most anyone with an interest in fantasy adventure stories, regardless of their personal strengths. AD&D was there for those gamers who enjoy more complex game systems. Hero was there for those gamers who wanted to exclude anyone who wasn't a budding computer programmer (I kid). I don't dislike 4e, and there is a lot that I really like about it, but it has proven to be a poor introduction to RPGs for the two new players in my group.
D&D 4e targets the "logical-mathematical" type of gamer and delivers a fantastically-designed game that runs smoothly and is relatively easy to learn. But I think that has been at the cost of its accessibility to gamers outside of that group. If you don't care about whether or not your fighter is balanced with Bob's wizard through all levels of play, if you don't care that your character's main activity in combat is rolling a d20 to see if you hit and then rolling damage, if you don't care about having a plethora of options to customize your character, if you a prefer fast-and-loose over a strongly tactical approach to combat, and if you're playing a fighter precisely because you don't want to have to maintain a list of "spells" to choose from, then 4e has little to offer you and learning it will likely prove to be an uphill battle.
And as an introduction to role-playing games for new players, the game should appeal to a broad group of player preferences. I don't think that 4e's appeal is anywhere near as broad as that of Basic D&D.