Hearthpwn

Overview:
Use Counterspell paired with Kabal Lackey to cancel his cheat spell, The True Lich.



Mulligan:
Mulligan for Kabal Lackey and Counterspell.

Stage One:
Turn 1 is Kabal Lackey and Counterspell. Then, for the rest of the first phase, play as defensive as possible and draw. Try and play the second Counterspell when you think he's going to use Anti-Magic Shell, because that spell can lose you the game. On turn 7, play Doomsayer, so you can skip the second phase.

Stage Two:
Hopefully you had a Doomsayer and could end it immediately, if not, continue to play defensively and try to end it quickly. You have a Blizzard and Flamestrike to buy you time. If he has a full hand during the second phase, use the Research Project and Coldlight Oracles to burn some of his cards.

Stage Three:
Once they are gone, use Frost Lich Jaina, the Water Elementals and your hero power to whittle down what he has remaining and when he's used his clears use Ragnaros the Firelord and get a second one from Jan'alai, the Dragonhawk.

We were both in fatigue by the time the match finished, but with all the lifesteal, it was never a real danger.

My other Frozen Throne / Icecrown decks:
The Lower Citadel
     Lord Marrowgar (Control Paladin)
     Deathbringer Saurfang (Patron Warrior)
     Lady Deathwhisper (Odd Dragon Priest)

The Upper Reaches
     Blood-Queen Lana'thel (Zoolock)
     Professor Putricide (Elemental Mage)
     Sindragosa (Kingsbane Rogue)

The Frozen Throne - The Lich King
     Jade Druid vs. The Lich King
     Face Hunter vs. The Lich King
     Elemental Mage vs. The Lich King
     OTK Paladin vs. Lich King
     Resurrect Priest vs. The Lich King
     Mecha'thun Rogue vs. The Lich King
     Murloc Shaman vs. The Lich King
     Murloc Warlock vs. The Lich King
     C'Thun Warrior vs. The Lich King