Why does pitot tube freeze at an altitude whose temperature is way below the freezing point?
First, AF 447 was flying into the top of a tropical storm. The air was much more humid and warmer than that of the standard atmosphere.

Next, in the absence of seed crystals or nuclei, water vapour or liquid droplets stay in the air down to temperatures of -48.3°C at sea level pressure without freezing. From the linked article:


  Droplets of supercooled water often exist in stratiform and cumulus
  clouds. An aircraft flying through such a cloud sees an abrupt
  crystallization of these droplets, which can result in the formation
  of ice on the aircraft's wings or blockage of its instruments and
  probes, unless the aircraft is equipped with an appropriate de-icing
  system. Freezing rain is also caused by supercooled droplets.


So it was the impact with the probe which caused the supercooled droplets to freeze.