I am not familiar with the bags you are talking about (our bread bags aren't stretchy), but this has a fairly straightforward explanation. Things that are elastic usually get stiffer when cold. This is part of why winter tires exist. There's literally less molecular movement.
You did say they stay crinkly/brittle even after warming up, though. This is likely due to another mechanism. When a solid is created from a liquid, there is typically some type of crystal structure (with notable exceptions like glass). A material can have multiple crystal structures due to how the molecules line up. Often, the crystals are tiny, so you don't see them, but you can have large crystals if something is cooled slowly. That's how you get gems.
When crystals start to form, they start to incorporate as much of the surrounding material as possible. When they run into a neighboring crystal, they run out of material. Unless they just so happen to line up perfectly, they will remain separate. The space between them, called a grain boundary, can be a weak spot in something like a diamond. In metals, more grain boundaries actually make things stronger, usually. This is because metal crystals can slide along the plane of the crystal. This is why blacksmiths will quench stuff; the rapid cooling leads to smaller crystals, which leads to more grain boundaries.
A metal won't completely form crystals from every available molecule. Every process happens over time, and cooling a metal down extra cold causes it to shrink, which can cause any straggler molecules to join up with the crystals, which makes the metal stronger. That's why some metal objects are "cryohardened".
The last factor is that changing temperatures can change the most energetically favorable crystal structure. Tin pest is a famous example where in really cold weather, tin can change from its useful form to a brittle crumbly useless form, and it can only be fixed by remelting it.
It's all a bit weirder with plastics cause they can be crystalline, non crystalline, or a mix, but my guess is you've changed the structure of it.