Low temperatures: Undervoltage?
The first thing to check is whether the micro and any other electronic parts are actually rated for less the 0&deg;C operation.  Cheap variants can be only good over the 0-70 &deg;C range, for example.  Most parts are available in a wider temperature range, but these are usually selected from the main batch and cost more.  Another way to look at it is that you can buy the rejects that only work over 0-70 &deg;C for less.  Unless you specified a wider temperature range, or the part always comes that way, it's quite possible that it's only rated down to 0&deg;C.

If you know the circuit is supposed to work at your temperature, then the battery voltage dropping is a real possibility.  The batteries are powered by chemical reactions, which usually slow down with colder temperature.  The open circuit voltage can go down, the internal resistance up, and the capacity can be degraded.

The main point here is that checking the datasheets should be the first thing to do, other than of course you should have checked them as part of the design and adjusted the design accordingly.

If the problem is the batteries, then first get the right batteries.  Instead of running the circuit directly from the batteries, you can use a switching power supply to tolerate a larger battery voltage range, and thereby use your batteries more effectively and get more usable energy from them.  The easiest would be a buck converter, so put more cells in series to get more total energy.  For example, four cells in series would allow them to be used until really dead before a buck converter can't make 3.3 V anymore.