If my opponent targets a "flippable" creature such as Thing in the Ice with a targeted spell such as Beast Within and while that spell is on the stack, I manage to flip the creature (by casting an instant and removing the last counter), does Beast Within fizzle because the original target (Thing in the Ice) is not on the battlefield (at least not in its original form)?
No, it's still the same permanent, just its characteristics changed. So long as the new characteristics still fit the targeting criteria, the spell will still affect it when it resolves.
First, Thing in the Ice does not Flip; it Transforms. The distinction is important because flip cards are a thing.
And second, it is still the same object after it transforms. Changing its characteristics does not mean it is a different object. Beast Within will still resolve since it is still the same object that Beast Within targeted.
So the same would hold true if Thing in the Ice was targeted by a card that affected a target creature such as Swords to Plowshares? That is, if Thing in the Ice was targeted by Swords to Plowshares and it transformed into Awoken Horror before Swords to Plowshares resolved, it would still be exiled even though the original target creature, at least in name anyway, no longer existed?
It is still the same creature. It just has a different name. Changing characteristics is not enough to make it something different. As long as it is still a creature (which it is here) means it is still a legal target for Swords and will still be exiled.
Spells and abilities may only target players and/or objects.
Permanents are objects.
Changing some aspects of a permanent or changing its status doesn't change the object it is.
It could be said that Beast Within does not actually target a permanent; it targets an object which must be a permanent, just as Swords to Plowshares targets an object which must be a creature.
109.1. An object is an ability on the stack, a card, a copy of a card, a token, a spell, a permanent, or an emblem.
110.1. A permanent is a card or token on the battlefield. (...)
110.5. A permanent’s status is its physical state (...): tapped/untapped, flipped/unflipped, face up/face down, (...)
115.1. Some spells and abilities require their controller to choose one or more targets for them. The targets are object(s) and/or player(s) (...)
Former Rules Advisor
"Everything's better with pirates." - Lodge
(The Gamers: Dorkness Rising)
"Any sufficiently analyzed magic is indistinguishable from science."
(Girl Genius - Fairy Tale Theater Break - Cinderella, end of volume 8)
And second, it is still the same object after it transforms. Changing its characteristics does not mean it is a different object. Beast Within will still resolve since it is still the same object that Beast Within targeted.
Permanents are objects.
Changing some aspects of a permanent or changing its status doesn't change the object it is.
It could be said that Beast Within does not actually target a permanent; it targets an object which must be a permanent, just as Swords to Plowshares targets an object which must be a creature.
110.1. A permanent is a card or token on the battlefield. (...)
110.5. A permanent’s status is its physical state (...): tapped/untapped, flipped/unflipped, face up/face down, (...)
115.1. Some spells and abilities require their controller to choose one or more targets for them. The targets are object(s) and/or player(s) (...)
RULES OF MAGIC :
http://magic.wizards.com/en/game-info/gameplay/rules-and-formats/rules