According to their description, frost worms are 40 feet long and 5 feet in diameter, and weigh 8000 pounds. Assuming they're cilinder-shaped, they're ridiculously rare at only 40 kilograms a cubic meter, which is less dense than styrofoam. If submerged in liquid hydrogen, they would float.
Frost Worms have 14 magical beast RHD, and are Huge. Their strength and constitution are quite high, their other stats average or cripplingly low. Movement-wise they can crawl and bury, even through ice. The worms have a single natural attack, but a mouthpick weapon is probably a better choice. They've also got the cold subtype, which is slightly detrimental in the average campaign but useful if one wants to go for a swim in liquid hydrogen.
Their various special abilities are more interesting. The unimaginatively named 'Cold' is a source of minor bonus damage against foes with natural attacks, but the breath weapon is very nice (though the recharge time kills it). Death Throes will probably do more harm than good and is unlikely to happen anyway (and how is the worm nonmagically turning to ice and exploding, anyway?).
Finally, there's the worm's unique ability Trill, a giant AoE that stuns, doesn't seem to have a set duration, is easy to immunize your allies to, and isn't even immediately broken when affected individuals get attacked. It's entirely possible for a frost worm to stun the entire battlefield then continue trilling as its allies fight the stunned enemies one by one. That said, as a sonic mind-affecting stun there's a lot of ways to be immune.
In the end, I don't think frost worms need a positive LA. 14 HD is a big price to pay for what's essentially a save-or-suck and boosted melee abilities. On the other hand, -0 LA seems unnecessary too: frost worms can, with the right optimization, contribute effectively to a party.