In my experience with newbies, even the Fighter (in 3.X anyway) is often too complex for people totally new to the game, because of all the feat choices. I would recommend Barbarian over Fighter for this reason alone- the only significant decision the player has to worry about is when to Rage. With Fighters, having all those feats to select from is essentially the same as having a lot of spells to pick from, even though the feats never get used up (typically).
Rogue is a decent secondary choice, but I have to agree with the poster above who said Scout is even easier thanks to the rules surrounding Sneak Attacks. That said, traps can be a problem, so a "trapspringer" rogue who plans on avoiding combat rather than getting into it may be a good newbie character.
There is no healer variant I would recommend to a newbie player- Cleric is far too complex, because (A) it involves preparing spells, the worst possible mechanic to throw at a newbie player, and (B) it involves several limited-use resources- not just the spells, but also Turn Undead. Sure, it doesn't require as much game-knowledge and finesse to play as a Wizard, but it's certainly no Warlock! Ultimately, Favored Soul might actually work best for this, since it doesn't prepare spells (even with the possibility of turning them into other stuff spontaneously, the whole spell-preparation thing is just a headache you want to avoid with any newbie) and doesn't have Turn Undead to worry about. The one gotcha with Favored Soul is the double-ability-dependent spellcasting. You might consider house-ruling that to just work off of one or the other, if you want to include a Favored Soul.
Spellcasters, I'd say Warlock hands down. It's by far the simplest of the spellcasting classes mechanically, with no limits on its use of powers and (at low levels at least) only a few actual powers to use anyway. Allowing retraining is probably a Good Idea for a newbie player, so they can try the different ideas (i.e. Invocations) out and see what fits them best. If the alignment restrictions will be a problem, then change them! You're the DM, use Rule 0. If there's concern about the demonic/fiendish flavor, then change that too, or provide a house-ruled version of the Warlock that has powers granted by Celestials- honestly, is there any reason why the Chaotic Good Angels or the Eladrins wouldn't create something like a Warlock, in the face of the existence of Fiendish ones? Remember, they're Chaotic! Their very nature is to break or ignore rules.
Another excellent spellcaster to pick is the Warmage, since its only difficulty (before getting the Sudden Metamagic feats) is tracking how many spells it has left. You don't even have to pick out a spell selection for the Warmage- it can cast any spell from its class list, at any time. It's a Sorcerer with a pre-selected spell list. For the same reason, the Dread Necromancer (from Heroes of Horror) and Beguiler (from PHB II) can work for newbies, though they both get more class features are are therefore more complex than the Warmage. I'd recommend a Sorcerer before either of them, to be honest, though for me the Sorcerer is in the "middle complex" range along with the Cleric.