It becomes helpless immediately
When a creature gains the helpless condition, others' actions on that creature gain benefits on it. It's safe to assume that if a creature becomes helpless, you get a +4 melee attack bonus even if it hasn't been that creatures turn yet since it became helpless. Deducing from that, the creature gains the helpless condition immediately when it has failed its saving throw, and the effects of helpless apply immediately.
It will begin falling immediately
It cannot use its wings and will begin to plummet towards the ground. In a single round, a creature can fall up to 500 feet, and every round after that it has reached terminal velocity and falls at 1,200 feet per round. [quotation needed]
Since the creature is falling less than 500 feet, it cannot cast spells and it is only allowed to take immediate actions. Having the helpless condition effectively prevents the creature from countering the fall before its own turn comes up. Since the fall distance is only 30 feet, it will also most likely hit the ground before its own turn comes up, but this is subject to factors like initiative order, GM fiat and desired amount of simulationist play. Because in a combat round, all actions kind of happen all at the same time, it's hard to draw a line whether the creature will in fact be mid-air when its own turn comes up. But even so, given that it's helpless and falling, there is really not much the creature could do. Because it's falling in this round, it can't use the full-round action required to break the ice before it hits the ground.
It will take fall damage (or does it?)
So let's say that the creature will slam into the ground that same round. Something interesting might happen. Depending how you rule it, when it slams into the ground as a big block of ice, the ice also takes damage. Icy Prison ice has a hardness of 0 and 3 hit points per inch of thickness. You could split the fall damage 50/50 between the creature and the ice, or threat the ice as damage reduction to fall damage. Regardless of how you split it, if the ice reaches 0 hit points because of fall damage, the ice would shatter and the creature would no longer be helpless.
When it saves vs. Icy Prison
To address your bonus question, let's visualize becoming entangled due to a saving throw as the ice spell having some sort of effect, but not the one that imprisons the creature. Ice crystals form on its wings and body at the point of impact, muscles stiffen and ache, feathers freeze and crack, and the creature will be able to keep flying, but at reduced speed and maneuverability.