In my roleplaying career I have encountered and run a wide variety of games, from things as light as Capes and Lady Blackbird, to middle-of-the-road games such as Dungeon World, World of Darkness (both universes), and the various flavors of FATE, to more mechanically crunchy games such as every edition since AD&D including the Next playtest and many of the d20 offshoots. And although I have never run a D&D campaign for new players, I have extensive experience running other games for new players (including a stint spent running a new game for a new set of players nearly every week), many - but not all - of which focused primarily on roleplaying which provides me with a great deal of insight into what does and does not help in such situations.
Not 3.5: As new players, learning the math can often interfere with actually playing the game. It is very easy to get bogged down in crunching the numbers which tends to block the flow of play.
Not 4e: 4e is a great game for new players in the sense that it is easy to learn the rules. The problem, in my experience, is that people new to heavy roleplaying benefit significantly from having roleplaying-oriented rules to latch onto. D&D 4th Edition does not have these. While you can always deviate from the prescribed path as a GM, by the RAW essentially everything in 4e was either a combat encounter or a skill challenge. The latter can lead to creative thinking (How do I apply my highest skills to this situations?) but left much to be desired in terms of encouraging player narrative.
Not Next: So, if the fact that it isn't out yet, (including the starter set; which may or may not be representative of the following products) isn't a good enough reason, my admittedly limited experience suggests that it plays very much like 4e. Other folks have more recent experience with it, so I would certainly take their input into account but I would also take it with a grain of salt until the final product is on store shelves.
What do I recommend?
While I can recommend various games that will feel like D&D (Dungeon World tops my list at the moment), I can't recommend any of the actual D&D games for new players to try a heavy roleplaying campaign for the first time. 4e will be fairly easy to learn, making it good for new players but in my experience it doesn't provide the sort of mechanical support to roleplaying choices that an introduction to roleplaying (over rollplaying) needs. On the other hand, while 3.5 provides an almost infinite list of options for customizing your character to support your roleplay choices the fact that many of these choices aren't available until higher levels coupled with the frequency of new numerical bonuses and penalties makes it not particular suited to new players. Based on my experiences, it is my belief that if you insist on sticking with D&D this is the choice you will have to make:
Good for new players (4e) OR Good for roleplaying (3.5) OR Next when it finally comes out (decidedly incomplete information available until sometime after August)