Additional thoughts:
Maexanna: Decent but nothing too exciting. She'll kill anything but poison minions tend to work better in theory than in practice.
Mad Scientist: Great for Mages. 2/2 + a free 3 cost Secret. Even if it's random (i.e. you're playing a lot of secrets), it's a good early game play. Hunter and Paladin are OK with him but I'm not sure I'd swap things out for him.
Sludge Belcher: The deathrattle makes him OK. I'm undecided on him though as he's just a Sen'Jin for 1 more mana that gives you a goldshire footman on death. It slows down aggro but on turn 5, aggro is looking to finish off the game. I'm not sold on him.
Stoneskin Gargoyle: At 3 mana he's in an OK spot but the 1 attack is a killer (and yet raising it to 2 attack power might make him overpowered). Again, not sold on him.
Spectral Knight: The new best 5 drop neutral minion in the game.
Zombie Chow: Great in the early game when player health doesn't really matter too much. At 1 mana he's the best turn 1 drop out there for most classes. The problem is that later in the game he's not just a dead card, he's a liability if he's actually played. I see him in Zoo Decks though.
Deathlord: The big beefy taunt doesn't really get offset by the deathrattle in my opinion. If your opponent can kill him on turn 4 and get a Ragnaros out of the deal... It's just more RNG in a game already cluttered with RNG mechanics.
Echoing Ooze: It's a cute card for 2 mana but his real strength is in later turn combos (drop an ooze and then drop a defender of argus and now you've got 2 2/3 taunters in addition to whatever else the DOA hit). Gimmicky though.
Haunted Creeper: I think he might be a bit of a sleeper. He's cheap with a decent deathrattle.
Kel'Thuzad: Win more. He's really powerful but at 8 mana I don't want to see a "weak" card. He reminds me a lot of Archmage Antonidas. If you can get him out cleanly, he will win you the game flat out. But if your opponent can remove him... On the plus side, you can drop him, sacrifice your board the same turn for board position and then reclaim your side before Kel'Thuzad gets nuked down. I think that's where he will shine. The most playable Legendary cards are the ones that give you a benefit the turn you play him (Such as Thalnos, Ragnaros, Ysera and so on). Overall I think he fits the theme of the expansion and he'll be viable in some decks.
Nerub'ar Weblord: Not terrible. I can see uses but not sure he's going to see a lot of use.
Unstable Ghoul: He's pretty good actually. A cheaper, weaker, Abomination but he really helps slow down aggression.
Wailing Soul: Too gimmicky and too situational to be useful.