|Interesting symptoms. All I can add is that if my 350D acts up, I can attribute it to hot, extreme climates. (above 100F, 38C)
I used the camera flawlessly through the winter in Germany and Austria in Dec/Jan 2007/2008, so regular winter cold (20F, -6C) didn't affect it.
If performed flawlessly in the wind blown cold if Iceland and Greenland in 2006.
Currently, I've got just about 10,000 frames on my 350D.
Sorry - no answers, but hopefully the additional data helps you troubleshoot.
Last thought, I would check the electrical contacts - are they clean on the battery and the contacts in the camera? Do you have a second battery to try, and see if the results are the same or different with the second battery. Makes sure the contacts are clean.