Why doesn't chocolate ever feel cold?
One possibility is that chocolate has a lower thermal conductivity than water-based foods, which make up much of the food in our freezers.

If you open your freezer and touch a cardboard food container, then touch a metal ice tray, which one feels colder? They are both the same temperature, but the metal tray feels colder because it conducts heat better than the cardboard box, so the heat gets transferred out of your hand quicker and it feels colder.  

Water is a relatively good conductor of heat and is present in large quantities in many foods. Chocolate is largely made up of fatty organics, which do not conduct heat as well. It is thus very possible that chocolate has a lower thermal conductivity than many frozen foods and therefore doesn't feel as cold to the touch in comparison.