Why do batteries not last as long in a cold environment?
Batteries don't rely on semicondutors, correct.  They do, however, store energy chemically, and rely on chemical reactions to create electron flow.  

Note that "last as long...in a cold environment" can be taken two ways--discharge duration under load or total useful life.  I'm assuming that you meant time under load, as nearly all batteries benefit from an extended useful life if stored at low temperatures.

Most batteries (ignoring a few more exotic flavors) use two metallic or carbon electrodes, separated by an electrolyte.  Current is produced by ion exchange (oxidation/reduction reaction) between the electrolyte and the anode and between the electrolyte and the cathode.

At reduced temperature, the internal impedance of the cell increases and the rate of ion exchange is reduced because the necessary chemical reactions progress more slowly.  This causes more power to be dissipated in the cell rather than in the load, and also reduces the peak current available from the cell at low temperature.  The cell doesn't last as long under load because less chemically stored energy can be converted to useful electrical energy.

This resource may be of interest.