I think Cold should still deal damage, but also apply an enhancement penalty to Strength/Dex (not damage). The reason for this: if you're cold, you start shivering and get weak. If you warm up, though, the effects go away and you're fine. Also, this doesn't make cold weapons/creatures overly powerful. Don't forget, ability damage only heals at the rate of 1 point/day unless otherwise stated, or you use spells. And, some wiseass will simply throw down a lesser restoration on a frozen character, healing all the abliity damage and magicall unfreezing him. If you make it an enhancement penalty, it's harder to get rid of without using the rules below.
Supernatural cold effects, though, could deal ability damage. I'm talking things like epic spells, the depths of space, or things like that, not just a dragon's breath weapon (unless it's special somehow).
Also, I don't know
where you got Wis as the determining stat - it should be Con.
I don't agree with your frostbite rules, though I can see where you're coming from. Not everyone who suffers frostbite loses extremities, though - if you're lucky, you get away with losing some skin, which eventually heals. Let's say that any time you suffer damage that reduces the ability score below half, you have to make a Con check (DC 15). Each time you fail the check, you take one point of Con damage. If one score is reduced to 0, the DC increases to 20 and any further failed checks become Con drain.
I think what you need are stacking effects, like they do with fear, panic, frightened, et al. - let's say some unlucky PCs are out in severe cold long enough to get really chilled (new effect; occurs when Str/Dex exceed half Con). They manages to make it to shelter in an old abandoned hut, start a fire, and get some warmth (but not enough to reverse all the penalties). Then, say, a frost giant attacks them, tearing the roof of their hut and exposing them to the cold. The defeat the giant (and his winter wolves), but have suffered more cold damage, bringing them down to the hypothermia level (or, in the unfortunate fighter's case, frostbite).
Now, the problem is, we have no rules for any of these effects. How much heat does it take to negate the penalties incurred from hypothermia? How do you go about uncrystallizing someone without melting them into a puddle of bloody slush? Freezing, BTW, is not just paralyzation, IMO - if you go by that definition, a simple remove paralysis will reverse the effect.
My suggestion: One hour at safe temperature negates 2 points of penalties. One hour at very hot negates 4 points. Anything above that would simply deal fire damage as before, because going from one extreme to the other is a bad thing in general. Additional effects, like a fire, blankets, warm water, etc. can serve to negate additional points (a small fire in a cold room/cave would be considered safe temp - 2 points/hour, while a larger fire in a warm room would likely push the temp up to very hot - 4 points/hour). The problem with crystallization is that ability scores don't go to negatives - 0 is the limit. This is easily fixed, though... the frozen condition occurs when either Str or Dex is reduced to 0. Crystallization occurs when both are reduced to 0. Someone who's been frozen or crystallized and is brought back by nonmagical means (i.e., building a fire nearby) must either a) receive a
heal spell after the first hour, or b) make a Con check (DC 15 for frozen, or DC 20 for crystallization) after the first hour or die from massive system shock. Being frozen and brought back is hard on the system, and if someone doesn't do it right (too much heat too fast, e.g.) it could easily kill the person.
Now, someone will inevitably try to drop a fireball or burning hands on the person to melt him; this could work, to a point - say, the person takes half/quarter damage (for chiling/hypothermia) or quarter/no damage (for freezing), but is reduced by one level of freezing. it's a crude method, but it would work, I guess. Someone who's been crystallized, however, has serious problems - he has the Vulnerablity to Fire ability. Additionally, if he's reduced to 0 hp through application of fire, he melts into a puddle of bloody slush, and cannot be brought back by anything short of a true res.
And of course, you could create new spells: warming hands, for instance - the caster's touch reduces the victim's freezing state by one (from hypothermia to chilling, e.g., reducing the penalties). Crystallize - flash-freezes the target (this one would likely be epic, or at least 8th-9th level). Hypothermia - an area of effect that chills the air, affecting all within it. Hmm... I might steal these for myself.
