That is a problem exclusive to Priest?
Anyway, most Priest lists run Museum Curator in that spot anyway, or the class Dragon. Now they can run Arcane Anomaly or Netherspite Historian in that slot if they want.
Arcane Anomaly coin PW:S seems pretty good to me.
Very few priests are playing with Museum Curator now. The 1/2 body does nothing. N'zoth as a main archtype is pretty dead (with no deathrattle effect.)
If you're playing Resurrect, you're not playing Northshire Cleric on turn 1 or turn 2. The only card you MIGHT play on turn 2 is Wild Pyromancer (against Zoo, perhaps?)
Only about half of priest decks are using Northshire Cleric. It's a dead card most of the time unless you can combo it with Wild Pyromancer. With 1 power, it doesn't contest anything except tokens created by Entangling Roots, Argent Protector, or the paladin hero power and it dies to almost every two drop in the game.
Priest of the Feast is "ok". No one is disputing that, but it's another "decent" four drop in a class that already has too many four drops: Shifting Shade, Holy Champion, the 3/6 C'thun guy, 4/2 C'thun guy, ASP, and Elise. It doesn't deal with the 4 mana 7/7. It doesn't deal with Totem Golem. It doesn't do anything against Dragon Warrior. It's not enough.
Same with the Bishop. He's OK. Sometimes he will get you a Sylvanas, Blademaster, or something big and it will be really good.
Thing is, Priest didn't need OK cards, they needed stronger cards because they are the weaker class.
I'm pretty excited about the neutrals we got, but I don't see Priest really rising in the tiers. Not like Warrior, who really shouldn't complain about anything seeing how much they completely DOMINATE the current meta.