You touched on the major thing I think. ASCII graphics and lack of a tutorial really hurt the game, and while from a community standpoint I think this is a good thing, as it tends to scare off players who don't want to roll with the punches, in terms of size this slows growth badly. Other problems:
1. Menus are painful to sort through. Once players get over the initial shock and into the management, they may find themselves digging through, say, the animal menu where animals are thrown in seemingly at random or trying to forbid/unforbid certain stones in the stones menu. Compared to even the rough organization of the kitchen menu (which seems to be arranged in meat->seeds->plants->drinks->processed cookables). Arranging stones by use and animals by species and gender would be great.
2. Army is a pita to work with. Much of this is being addressed in the next version, but a better interface for dwarves switching to training weapons between sieges or ambushes would be a godsend. Currently, if I let my dwarves spar with unmodified iron warhammers I usually end up with internal injuries, but I don't dare have them try to switch to silver in the event of an orc siege. Granted I'm playing with the military difficulty ramped up, but even then, for mature fortresses in vanilla this is the same problem.
3. Traps. Traps are too damn good, to me this is actually a turn off. There's no real incentive to build an army if you can line an entrance corridor with 50 rows of weapon traps, but at the same time building armies is so much fun. To go along with military improvements, a change to traps would, I think, go a long way toward improving the game for newbies.
4. Ambushes suck. If you aren't reading a walkthrough and pre-warned about them, they can really wreck your day. Something smaller than a single squad siege but visible unlike an ambush would be a good way to introduce new players to combat. The attacks from underground creatures might help with this.