I'm not sure where I heard it, but one idea that I like is that it ties to the Big Bang and the expansion of the universe. Most people don't realize how complicated conservation laws get in general relativity. For instance it is a matter of opinion whether or not energy is conserved! (See http://www.math.ucr.edu/home/baez/physics/Relativity/GR/ener... for details.) In particular suppose a photon sets out on a long journey, gets red shifted by the expansion of the universe, and consequently loses energy. What happened to the energy of the photon?
This question is highly relevant to the issue of entropy. Current theory says that we had a very hot and almost uniform universe, which then expanded rapidly. As it expanded any clumps that formed stayed hot, while the space between them cooled off, thereby leading to an increased thermodynamic non-equilibrium. Worse yet, local gravity pulled the clumps together resulting in interesting things like stars, which further increased the amount of non-equilibrium stuff going on.
Of course this pushes the question of the arrow of the time down to cosmology and general relativity. But given that physicists debate whether conservation of energy makes sense in general relativity, I'm fairly comfortable with accepting that the laws of thermodynamics are on even shakier ground there. Which makes the physical asymmetry seem not so bad to me.