Different theory(s)

1.) The book opened with Fain corrupting the trollocs, changes were visible. Could Fain be corrupting Aiel he encounters as well? It would explain the visible changes in the Aiels looks, and actions.

2.) They may be from the world of the Snakes and Foxes. There is always a price to be paid. Perhaps, when Mat cut his way out, he left a door open that allows them out of their box. Before, you only heard of people traveling to them. Surely, these creatures would have traveled to Randland and beyond if they had the chance. I think this theory is supported by the fact that Olver was able to win snakes and foxes afterwards. Mat had cheated to change the rules, and now that the rules are changed, the game can be won. But at what cost? Perhaps Olver winning the game is an omen of some sort, something lost in time that was watched for by the people who first crafted the game to teach the children about the dangers of the tower?

3.) This one is complete nonsense, but I like it anyhow. The dark glassy eyes and the filed teeth, along with the way they move remind me of a shark. Maybe the Sharans have some sort of ritual like the Seanchan have to create assasins, only instead of being shadowed, it transforms the person into a sharklike creature. Perhaps, it simply is the process they use to create their soldiers. There is much unknown about Shara, but they are in close proximity to the Aiel, and it is possible that they have captured several and converted them. Avi's viewing showed the Seanchen Empire building a road across the waste. The road was undoubtedbly going to Shara. Was it for a trade route? Or was it for conquest? Perhaps, the Sharans had been (will be) meddling in their affairs a little too much?

I like the Fain theory the best, as the prologue did open with Fain twisting trollocs. I have a feeling that the dead area of the swamp that Galad and the Whitecloaks passed through had been more of Fains influence as he traveled and less of the Dark Ones.

But the fact that snakes and foxes can now be won cannot be discounted. Was there another price for Mat being given the means to escape? Are the Finns now released on the world to gain succor through the release of emotion? I note that it never says that anyone was killed after the veil was removed...