I think the biggest draw of D&D is the fantasy, storytelling aspect. I doubt anyone starts by thinking, "Man, I really wanna be a rules lawyer!" The problem, therefore, is mechanics:
I have never, ever liked making characters. Oh, I love creating a backstory and all that, but the actual numbers stymie me. I've played many times and know the rules well enough to play and play successfully, but whenever I make a character, I always ask someone to check my sheet for me.
The same thing happens during play. Usually combat, but not always. It goes like this:
"A large group of humanoids crests the ridge. The leader appears to be wearing a cape of animal skins and is wielding a wicked-looking club with stones embedded in it. He shouts something in a language you don't understand, and suddenly the group is charging down the hill at you."
"I pull out my shortbow and take a shot at the leader."
"Ok, roll initiative."
And from that point, it gets tedious. New GMs (who haven't played much before) get lost in the numbers and players get bored with it. Sometimes confrontations get bogged down when people have to look up things in the sourcebooks.
There has got to be a way to streamline the system so that people who don't care too much about the numbers can get a balanced character and a balanced game together with little to no crunching. Perhaps this is just me, but it was enough that when I was trying to teach myself Magic (years and years ago when it first came out), I gave up and didn't come back to the game for another 10 years and that was only because someone I knew played and persuaded me to let him teach me. In that case, the "complicated" rules put me off the game. It would have been the same for D&D if I hadn't had someone holding my hand from before I even bought my first PHB.
Caveat: I don't know anything about the starter set. Also, I've seen D&D for Dummies out recently, but I haven't had a chance to actually look in it--is it any good? Can someone play from that book?