This answer is about cold denaturation of proteins rather than the effect of freezing.
The folded structure of a protein is thermodynamically stable as a result of a small favourable difference between the free energies of the folded and unfolded states. For a small single-domain protein this difference is usually only equivalent to the strength of a small number of hydrogen bonds - folded states are not very stable.
Electrostatic interactions, hydrogen bonds, and van der Waals interactions within the protein, interactions within the solvent, and interactions between the protein and the solvent all have to be considered, together with any entropic effects.
One factor that plays a part is the effect that an exposed non-polar group from the protein can have upon the solvent. Because the water molecules next to such a non-polar group cannot form hydrogen bonds with it they become more ordered or ice-like as they can only hydrogen bond with each other. This is the basis of the hydrophobic effect - as a protein folds and sequesters its non-polar groups in the protein interior then the unfavourable entropy change in the protein (i.e. it has become more ordered) is offset by the increased disorder in the water.
As the temperature falls the water becomes more structured anyway, so an increase in entropy of the water is no longer available to offset the decreased entropy of the folded polypeptide. The thermodynamic balance sheet is altered and the unfolded state is favoured.