Some electrolytics can effectively freeze if you get them too cold. I see -20 or -25C as a pretty common "storage temp" spec. Good caps are often good to -40C or -50C when not in operation. Operating temp ranges a little more, and there is a capacitance dependence on temperature. The older the cap, the worse this dependence is likely to be both due to aging effects and the fact that newer caps tend to have better such design characteristics compared to older ones to begin with. If the cap is really far off, it may go out of design tolerances and cause problems.
One big issue with cold caps is that they sometimes get heated up rather rapidly due to ripple current heating the cap internally or due to external heat sources when powered on. If this is done quickly enough, the cap can break at a stress point, which often results in the cap leaking or venting. Device failure would usually result from this due to either the leaking or from the sudden change in characteristics of the cap.
A small failure from thermal effects (which might otherwise not be a problem) might cause the cap to be unable to withstand the voltage or ripple current being applied to it, resulting in further failure. This is more likely to occur as lower spec margins are provided in the design (which is typical of modern designs). Then again, maybe you want to notice the issue quickly.
Of course, condensation at cold temps near freezing is also a major problem, as Ken mentioned.
In general, figure if it's above freezing and things aren't wet, you're probably good. If it's below freezing but above -20C, and condensation doesn't appear to be a factor, you're probably good as far as caps go. Of course, if you're talking about powering up an arcade game in the cold, CRTs also suffer from the whole rapid temp change thing (especially since they've got their own heaters), and failure of a CRT is far more spectacular
