Have you evaluated the approach of running a low clock speed ( 4Mhz) and running the Arduino directly from the battery? This might work for you, unless you require the USB Function.
On another note, you might consider a conformal coating on the board. I would consider one of the silicone spray conformal coatings available at electronics suppliers.
Another thought: Not knowing the high temperature the system must contend with, but for the lower temperatures It might be worth considering an insulated housing whose goal is to keep the internally generated heat in the package in order to warm the battery and circuit.
Before deployment you should attempt to thermal cycle the device as much as you can and as many times as you can. This will precipitate any marginal connections.