Re: Should there be 'freezing protection' ability?

You are right, I totally forgot about that one. Well, there is the "can't be damaged" thing, but I guess that there can be a "purify zombie" card as well.

Like: Something something, zombies cannot have deadly.

From the counters... I must disagree with you. Knowing what zombie is under what gravestone is something really useful. You can know what lanes to avoid (like Smelly Zombie or Jester, and what lanes you TOTALLY must defend (like Exploding Imp or Stealthy Imp).

Freezing them is also super good, just like freezing any other card. You avoid the damage, and can clear them on the next turn. Yes, sometimes it has little to no effect, like freezing a Pogo Bouncer, but it can save you from things like Line Dancing Zombie, Tomb Raiser Zombie or an Abracadaver.

Another hilarious thing is that, if you have Winter Squash on the field and you play the Cool Bean, it will destroy all the frozen gravestones.

To be honest; I think Gravestones are pretty balanced right now. The mechanic didn´t get to much quality additions lately to keep up its oppressive nature and most Gravestone decks play very simliar, generic lists that are easily anticipated. It was much more of a deal when people still experimented more and you really never knew what to expect.
Right now I feel the only really problematic Gravestone is the pogobouncer. And most of that because the lack of counterplay makes it VERY VERY frustrating to play against it.

How many people here actually had the situation where the opponent dropped a gravestone and it was SUPER OBVIOUS it was a bouncer but you lost anyway because there is no reasonable counterplay?

I think roots should have an additional lord along the lines of:
"Roots you control cannot be moved or bounced by abilities or tricks you opponent controls"

as a sort of "soft" untrickable mechanic.

I agree that preemptive countering is a fairly interesting thing that should be looked into. things that alter what "the next XY card" does.

examples:
"when played:the next Plant/Zombie played does not trigger any abilities"
"when played:the next time each player would take damage prevent that"

as for deadly:
There are very very few problematic deadly cards around....toxic imp because of amphibious is probably the "worst" of them. I still think that doesn´t need much balancing. The only thing I can complain about here is that a few tricks can be tweaked in an almost unfair way by getting conjured or lords. cakesplosion can have deadly for example and even worse; science tricks with bullseye.

I would like to see a chumping-counter though maybe even for both sides. example:
3 brains/suns 2/2 "when a plant/zombie is played here, get untrickable and invulnerable for the rest of the turn."
I guess that would do the trick. Arguably better with frenzy or double strike but I didn´t want to think about how to price that. 

to be honest; I think they should rework deadly altogether or offer an alternative effect of simliar but slightly lower value. Deadly is just hard to balance because it´s so unconditionally powerful. 

my proposal would be a withering effect that doesn´t do dmg to the zombies power but assignes it as -x/-x to the plant. which would be very strong but more predictable, easier to balance and in the end; you can slap it on more cards without regret

to be fair; all classes have weaknesses if you look at them alone.