@brianjakub,
Living in a new environment is not evidence of an increase in complexity. Mammoth always had hair. Some mammoth had longer and heavier hair. A change in the environment, which we call the ice age, created an opportunity for the mammoth to exploit the vast grasslands of the periglacial regions, where no forest could survive (under those conditions). The mutation was always there--no change in reproduction and no complex processes were necessary for those mammoth to exploit the opportunity.
Your "new information" bullshit is just that--bullshit. When the environment changed, those mammoth with the long guard hairs and the undercoat were able to exploit it. When it changed again, those mammoth, which had continued to evolve more long guard hairs and more undercoat, were doomed. There were no more complex processes, there was no "new information."
All you do is demonstrate that you do not understand natural selection. You're so addicted to your magic sky daddy superstition, that you shudder at the very thought of random events. What furthers reproductive success is retained, what hinders reproductive success dooms a species. There is no more striking example of this than the woolly mammoth--both the successful exploitation of environment, and the subsequent extinction when that environment changed.