It usually takes a lot of time to reach the freezing point ( FP)when conditions outside are severe. When this point is reached do not think that the whole fuel will became solid, the queroxene will be still a fluid, first problems will arise at FP-10ºC know as Pouring Point.
If the FP is reached you have to "heat" your fuel, descending to warmer FL or speeding up. None of these remedies are very effective because it take a lot of time to warm up the fuel as well. If speed is increasd 0.01M, Rat will increase 0.5ºC after ONE HOUR depending on aircraft type, tanks considered and fuel quantity.
FP for JET A-1 -47ºC, and fuel is not usually served below 5ºC even in the most severe weather conditions.
If you want to know more check "Polar Route Operations".
http://www.boeing.com/commercial/aer...ar_story.html.