How can the average coldest day of the year be before the winter solstice?
I have created composite plots from reanalysis data for the dates as partitioned in the image in the question.  I used the full NARR dataset, which covers 1979 to 2014, so I have a few more years of data than is included in the image above.  

What can be seen are largely wintertime climatological means.  A persistent subtropical high off the California coast and persistent lows in the north Pacific and Atlantic.  What does change is the mean extent of arctic air which descends into the US as winter progresses and retreats as spring approaches.  

Composite NARR MSLP and 500-1000 hPa thickness 1979-2014




Figure 1. From left to right, top to bottom the dates composited are Dec 1-15, 16-20, 21-25, 26-31, Jan 1-5, 6-10, 11-15, 16-20, 21-25, 26-31, Feb 1-15, 16-28, Mar 1-15 and 16-31.  MSLP is contoured every 4 hPa.  Thickness is shaded at intervals of 10 dm.  Click the plot for a larger version.

The signal I can pick out of this is the approaching and retreating cold (using the proxy of 1000-500 mb thickness) that seems to correlate well with the latest dates of cold in the eastern US, particularly in the great lakes and northeast.  

What I'm seeing in the west is that initially the subtropical high is broad and surface flowing westerlies impinging on the west coast would originate initially at higher latitudes than the do later in the winter.  By January the subtropical high and the low in the north Pacific have re-oriented so the surface flow is coming from around Hawaii.  The western US will also be subject the reduced seasonal temperature fluctuates from its proximity to the Pacific.  Once the area has cooled and equilibrated with the Pacific, temperatures will be stable.  As the continental landmass would lose more energy and cool, the westerlies coming off the Pacific (now relatively warm) counteract this tendency.  Conversely the east with mostly continental air flows experiences large seasonality and has a long-lasted source of very cold air from our neighbors to the north.

Summary

The west ceases to cool once it equilibrates with the Pacific, which looks like it happens early in winter (because even though the Pacific is cold, it isn't that cold).  Westerlies from the ocean heep the west warm.  East of the rockies there is no influence from large bodies of water and a constant source of cold arctic air and so the east continues to cool throughout the winter, until the pattern changes toward spring (and all the snow melts...).

For a smaller scale example of how water can have this influence, take a look at during the next extreme cold event in the midwest and great lakes, particularly when air is flowing westerly across Wisconsin and into Michigan.  You will observe a large temperature gradient across Lake Michigan, which keeps Michigan warmer (sometimes much warmer) than Wisconsin.  Later in the winter when the lake is frozen, that benefit is lost and so Michigan tends to be cooler later in winter as it is no longer "shielded" by the lakes.  

Data

Data was downloaded from NOAA's North American Regional Reanalysis, accessed 17 Feb 2015.  Files accessed include:


ftp://ftp.cdc.noaa.gov/Datasets/NARR/Dailies/monolevel/prmsl*nc
ftp://ftp.cdc.noaa.gov/Datasets/NARR/Derived/pressure/hgt.day.ltm.nc