I guess we need to agree to a definition of "change". Here are the common definitions:
1. To make or become different
2. Make or become a different substance entirely
Now, in regard to the first one: to become different. This is when the qualities of object go from one way to the next. For example, we say "the traffic light changed from red to green". Now, the traffic light is still a traffic light, but it has gone through a transformation in which its qualities and its purpose are now different. Perhaps more closely related to our discussion would be when the demeanor or personality of a person is altered. A person who was at one time a happy, outgoing person returns after some time and is now a depressed, angry cynic. We say to that person "you've changed". The person is still himself, but with drastically different qualities. This is the type of change that occurred between the OT and NT in God and the relationship between Him and Man. He is still considered the same "God" yet each have clear and distinct qualities. One is of order and justice, while the other is of love and mercy. Now, even if God stresses a particular quality at one time or another, this fluctuation in trait is still a shift.
Definition two implies that the very object becomes an entirely different object. A proper illustration is the growth of a seed into a plant. We no longer call a flower a seed, even though we know its history. A less accurate, but still sufficient example is the transformation of a caterpillar into a butterfly. Considering that God is without physical form, and can only be judged by His qualities, we have to admit that this change did in fact take place. Although it has been argued, there is little evidence of consistency between OT and NT. There is no cherubim guarding the gates, there isn't any fire and sulfur raining from the heavens, there are no tests to kill a loved one. In fact it is the exact opposite. Therefore, if God is measured by His qualities, and His qualities certainly did see a change, then the only conclusion under this definition of change is that God has changed form.