The Mage Storms were caused by the Cataclysm, when the magic released temporarily scrambled the world's magical patterns, effecting the physical world as well. The original set of storms followed on the heels of the Cataclysm. The first Storm was the worst, gradually tapering off. Creatures caught in the Storms could be killed or changed in various ways.
Mages were also changed by the Storms. Some powerful mages found they had permanently lost much of their abilities. Other minor mages suddenly found themselves with Master-level potential they had not possessed before. The Storms also worked on the personalities of mages, in extreme cases turning some into sadists and others into hermits. All the Kaled'a'in and their evacuation party, whether mages or not, were affected in subtle ways that resulted in oddities such as an abnormally high percentage of male newborns.
In the wake of the destruction and havoc of the Storms, there were no centralized governments left in the northern part of Velgarth. The largest level of organization was the small town or former army fortification. Some refugees made it as far as the Wtasi Empire located on the shore of the Salten Sea to the east. They sent back reports on the devastation and collapse of civilization in the lands Ma'ar had controlled. Some places, especially large cities, had been entirely dependent on magical Gates for food and other supplies. With the collapse of the Gates, the people starved. And with the onslaught of the surviving soldiers, chaos descended.
A millennium later echoes of the magic released came back around the world causing a second set of Mage Storms. These ran in reverse, starting with the mildest of the original Storms, and working backwards towards the initial explosion of the Cataclysm itself. As with the original Storms, these created what became know Changecircles. People, animals and plants caught in the Circles could be transported elsewhere, changed or killed in various ways. As the Storms worsened they were combated by Firesong, Karal, An'desha, Altra, and a number of others to prevent the total destruction of the original Cataclysm from repeating.