Why are proteins in the insoluble form when they are in frozen water?
If proteins change from being water soluble to water insoluble it means that their three-dimensional structure changed, because this determines how the protein interacts with the water. Most proteins have hydrophilic residues on the outside in their normal structure configuration, which makes the soluble. If this changes and some of the hydrophobic residues come to the protein surface the protein may not be soluble anymore.

The process of the structure changing (sometimes also called 'denaturing') can be caused by a lot of different factors - basically everything that is different from the inside of a cell (for humans: ~37°, salt concentrations, ...). If water freezes then the ice-crystal lattice can force the proteins out of their normal conformation/structure, after thawing the ice they may not get their structure back on their own (this depends on the protein).

To give an answer to your edit: the temperature does not affect the solubility directly, the effect is indirect through a change in structure