Crazy. FFZ just explored this idea, and while I'm not 100% satisfied with our result, it's something that solves the dilemma, even if it's not a simple one-prong solution to the problem.
The FFZ solution works on a few different angles:
#1 is rarity in monsters. Resistances and immunities and "eater" abilities (taking damage as healing) is limited to basically certain boss monsters and obvious elementals -- monsters that are supposed to be an unusual challenge, and so will need a different kind of strategy to handle.
#2 is variety in PC's. There are no "pure elemental mages." Much like the elemental ninjas of Naruto, any "elemental effects" are actually expressed on a few different levels. If you're a fire mage, you're not just doing fire damage -- perhaps you're healing, causing Berserk, using a weapon like the Axe, etc. You can't be a one-trick pony like that. And, there are options for lowering the resistances of enemies to various elements, if you take up that vanguard. Most parties should have access, even if only in item form, to any elemental energy that they may need.
To use the example from Mearls's blog, there's a lot more to "Ice Wizard" than cold damage -- piercing damage (from icicles!) and obscuring effects (from snowstorms!) and effects that knock prone (suddenly slippery!)...cold damage will never be all that you do.
#3 is a trade-off of resistances for vulnerabilities and transformative effects turning damage into "other stuff." If the boss monster is immune to fire damage, fire damage might still do SOMETHING to them (blind them, give them a penalty, reduce their SPD, SOMETHING!). Even if the boss is truly immune to Fire, he should have a vulnerability (say to Ice or Water or even something weirder -- there is no strict duality).
#4 is flexible character choice and adventure choice. Chances are good that even if you have an "ice wizard" who can't damage yetis for crud, you also have two or three other characters that might work in the adventure, and have a choice of two or three other adventures that don't involve yetis.
In tandem, these things basically patch the problem so that it's not a problem. I'd prefer to do it from the ground up, but resistances and immunities are part and parcel of the source material (true in both FFZ and in D&D), so what's left is to find a way so that your "ice wizard" can still work in a land of ice.
I approached Naruto and Avatar and the FF games (which hand out vulnerabilities like candy, but are generally choosier with immunities, and always have diverse character abilities), and these things gave me the answers FFZ used.
Overall, I like OBE's idea better than Mearls's. Making combat more dynamic like that, as others have pointed out, doesn't solve some of the more onerous problems (ice mages STILL aren't good in icy campaigns). Treating them more like weapons is a very good idea, but you don't want to get into the "ice = immobilize" thing either, because then a creature that can't be immobilized offers you the same problem as a creature that can't take ice damage.
Ultimately all the solutions share this:
An element is not just a type of damage.
The easiest solution, of course, is just to hand out "elemental specialist" feats that help you ignore a chunk of resistance.
There's a lot of ways to hit this problem.