CPU's work better at lower temperatures because wire RC flight time improves because the resistance of the wires improves, and more significantly because the mobility of carriers improves at lower temperatures.
On die wire resistance (near 25C) decreases by about 0.4% per degree Celsius improving the RC wire delay. CMOS transistors speed by at lower temperatures due to increased carrier mobility. The increase in mobility leads to improved saturation velocity which increased current driving capability. There are three factors, called scattering mechanisms, that influence mobility with decreasing temperature: phonon, surface and Coulombic scattering. Phonon scattering is the dominant scattering mechanism at room temperature and is caused by lattice vibration. At approximately 80K, Coulombic scattering caused by impurities becomes more dominant as the effect from phonon scattering becomes less significant, and surface scattering from charge traps also starts to have an impact on mobility. nFETs improve slightly faster compared to pFETs due to the changes in temperature dependent mobility between electron and holes.
There are two concerns with lower temperature operation: increased noise, analog circuit operation and high-speed circuit issues. Noise increases with decreased temperature because the switching delays are decreased (from lower RC and faster FETs) leading to higher frequency transients. These signals can more effectively couple across wires due to the reduced resistance. Analog circuitry may not be properly characterized for extremely low temperature operation. Also, circuits that are designed to require a certain delay - such as pulse latches - can see the delay decrease to the point where they induce a failure.