What does the snowflake with temperature symbol on an approach plate mean?
From FAA INFO 15002:


  A [snowflake] -XX°C icon will be incrementally added to airport approach plates, beginning Mar 5, 2015. The
  icon indicates a cold temperature altitude correction will be required on an approach when the reported
  temperature is, “at or below” the temperature specified for that airport. 


This looks to be a work-in-progress, as they started adding the icons in March, and compliance with applying the cold temperature altitude corrections becomes mandatory in September, 2015.

More info from the NBAA:


  Background: In response to aviation industry concerns over cold weather altimetry errors, the FAA
  conducted a risk analysis to determine if current 14 CFR Part 97 instrument approach procedures, in the
  United States National Airspace System, place aircraft at risk during cold temperature operations. This study
  applied the coldest recorded temperature at the given airports in the last five years and specifically determined
  if there was a probability that during these non-standard day operations, anticipated altitude errors in a
  barometric altimetry system could exceed the Required Obstacle Clearance (ROC) used on procedure
  segment altitudes. If a probability, of the ROC being exceeded, went above one percent on a segment of the
  approach, a temperature restriction was applied to that segment. In addition to the low probability that these
  procedures will be required, the probability of the ROC being exceeded precisely at an obstacle position is
  extremely low, providing an even greater safety margin.
  
  Action:
  Pilots must make an altitude correction to the published, “at”, “at or above” and “at or below” altitudes on
  designated segment(s) (see list below), on all published procedures and runways, when the reported airport
  temperature is at or below the published airport cold temperature restriction. 
  
  Pilots without temperature compensating aircraft are responsible to calculate and make a manual cold
  temperature altitude correction to the designated segment(s) of the approach using the AIM 7-2-3, ICAO Cold
  Temperature Error Table.
  
  Pilots with temperature compensating aircraft must ensure the system is on and operating for each segment
  requiring an altitude correction. Pilots must ensure they are flying at corrected altitude. If the system is not
  operating, the pilot is responsible to calculate and apply a manual cold weather altitude correction using the
  AIM 7-2-3 ICAO Cold Temperature Error Table. PILOTS SHOULD NOT MAKE AN ALTIMETER
  CHANGE to accomplish an altitude correction.
  
  Pilots must use the corrected MDA or DA/DH as the minimum for an approach. Pilots must meet the
  requirements in 14 CFR Part 91.175 in order to operate below the corrected MDA or DA/DH. Pilots must
  see and avoid obstacles when descending below the MDA.
  
  The temperature restriction at a “Cold Temperature Restricted Airport” is mutually exclusive from the charted
  temperature restriction published for “uncompensated baro-VNAV systems” on 14 CFR Part 97 RNAV
  (GPS) and RNAV (RNP) approach plates. The charted temperature restriction for uncompensated
  baro-VNAV systems is applicable to the final segment LNAV/VNAV minima. The charted temperature
  restriction must be followed regardless of the cold temperature restricted airport temperature.


There's more info in the NBAA document (I only included the exciting parts), including a list of affected airports, listed by state.  Lots in Alaska, none in Florida, unsurprisingly.  Applying this in flight looks like an absolute can of worms, as far as I can tell from the examples presented.

We'll probably see more come out about this as cold weather approaches, so stay tuned!