It's too bad we don't have some kind of data structure that is automatically replicated to all Bitcoin nodes, and has some kind of "fee/KB" mechanism to discourage spamming it.
I'm not sure that I'd want to promote mined transactions as a jamming resistant communications channel. Especially since, you know, it's not actually jamming resistant, and it's not hard to imagine examples where the miners would actually be interested in jamming NAKs on an update.
NAK's in the blockchain don't need to be exclusive though. For instance the protocol can be that NAK's are just some signed data, and you don't care how you get the data. For some scenarios putting it in the blockchain is great - the dev team goes crazy and backdoors the RNG - for others you're going to have to hope some other jam-proof communication mechanism works, like P2P distributed alerts or DNS seeds or whatever.
The big advantage of the blockchain is that many attacks aren't going to be very useful unless the target is synced with the network. Someone might, say, backdoor the RNG or make transactions be signed using nonces the attacker can predict. But users whose clients do manage to sync with the network will see the alert and not upgrade, and the ones that don't (because the attacker isolated them) are likely to do fewer transactions because they notice their client is acting funny and tx's aren't confirming or whatever.
Obviously the attacker could also fake parts of the GUI to make it looks like tx's are confirming, but now the number of lines of code they need to hijack just got even larger, making the attack even ever to spot.