Thermal Paste on Cold Side of Peltier Freezing and not transferring "Heat", what gives?
Yes, of course. A thermal paste intended for CPUs is rarely used below 25C. You need to read their datasheet or search for cryogenic thermal compounds.

It is probably cheaper to select some of the consumer grade ones through their datasheet and test the best for your application. Arctic Silver 5, for example, claims to be stable down to -50C.