Nice deep question.
Let's simplify by considering only the background radiation, without worrying about stars etc. Two things have happened to reduce the density of that background radiation, so that its temperature has dropped.
1. Since the universe has expanded, the photons are more dilute. By itself, however, that would not change the net photon energy.
2. The wavelengths of the photons have stretched out along with the expansion, reducing the energy per photon. This effect does seem, at first glance, to violate conservation of energy.
The resolution is somewhat over my head, but I believe it runs something like this. There's a negative gravitational potential energy density associated with the density of energy. As the energy density drops, this term becomes less negative, leaving the total energy conserved. However, I believe that there is some dispute as to whether this treatment is useful and whether the idea of global energy conservation ought to be preserved in cosmology.
Here's what looks like a good discussion:
http://blogs.discovermagazine.com/cosmicvariance/2010/02/22/energy-is-not-conserved/Mike W.
(published on 07/25/10)
