Frostbite's cooldown and cost should be tweaked downward so that her damage-to-mana or damage-to-CDR ratio is less affected by the nerf, in my opinion. At the moment the change only really makes her learning curve more punishing without actually affecting players at the top. That is to say, she's already a very binary champion (i.e she either deals no damage or 4x damage) - and this change will just widen the gap between an "I'm learning Anivia" player and a competitive player (and I've presumed this nerf is in response to her competitive presence - if you're actually nerfing the ability for new players to pick her up because you feel she's being mastered too easily, then I will concede this point).
But from the perspective of someone who see's a lot of people struggling to learn her, I think if her E was cheaper, or had a refund (similar to Annie), or was cheaper AND on a lower cooldown (thinking back to some of Lissandra's changes) - then maybe she wouldn't feel so bad missing one skill and consequently doing nothing since her damage is too poor _to waste the mana_.
Regarding the mechanic change itself, could the interaction not be expanded to more simply be (I know, "expand" and "simplify" sound oxymoronic):
> Frostbite deals 1% increased damage for every 1% that the target's movement speed is slowed, increased to 100% versus immobilized targets.
This could either:
* Factor all slows and stuns, not just Anivia's. (Yes please!)
* Factor the target's current movement speed (factoring depreciating returns, as well as being countered by Slow Resistance).
* Factor only the raw slow values (i.e. the strongest slow affecting the target).
This could mean Frostbite deals 20 / 30 / 40 % bonus damage based on ranks in R versus the current "Chill", increased to 30 / 45 / 60% bonus damage while Glacial Storm is empowered; and would deal 100% bonus damage versus targets stunned by Flash Frost. EDIT: Although saying this, has the passive on Glacial Storm been removed? The tooltip doesn't mention anything any more.
(P.S. If you do allow inter-champion interactions, don't forget to cap the slow modifier - since bugs like Janna's over-100%-slow seems to occur whenever a scaling on a capped-stat is introduced).