I have a minor amount of experience here, I'm running my ReallyBareBonesBoards at 3.3v 16mhz (overclocking, technically), and they start to crash randomly at 38*f, and lock up completely at 36*f.
It sounds like more voltage allows colder operation, but if you're already at 5v there isn't much more you can give it before you're overvolting the chip...
You're not running a USB interface, so it's clearer now that we are talking about the ATMEL chip's behavior at low temperatures.
My son designs Wind Energy dataloggers that run on very cold mountaintops (http://nrgsystems.com
). With ATMEL chips.
...SO I'll ask Him