I just thought of a theory that there are two sides of the Children of the Forest. One side focuses of nature (the side Bran is with). This side wargs into life--plants and animals. The other side, the Others, were Children who separated from the life-based Children during the War with First Men and began focusing their warging abilities on how to control the dead to defeat the First Men. When the life-based children saw that they had begun to succeed, they allied the First Men to defeat these abominations.
The reason the Others are creatures of ice is because they abandoned the forests and the weirwoods to commit to the cold and the dead, and began to adapt. The CotF survived off of the forests and acquired a fitting appearance. If the Others survived in the cold and in ice, then they would adapt as well. There may be magic that influenced this as well. Also, perhaps their icy language is a dialect of the True Tongue.
Now, the Wall came after the Long Night. The CotF allied the First Men in the Long Night, so after defeating the Others, who better than to teach you the magic to block the Others than their "cousins." I do not recall ever seeing that the First Men had a grasp of magic, nor giants who may or may not have assisted Brandon the Builder in raising the Wall. So that leaves the Children.
I don't know if this specifically has been suggested. The search didn't bring up anything relevant. As with most of my theory posts, this is thought-provoking. I want the help of the asoiaf community in finding out if this is a possible theory.
[Added 2/6/12] The Night's King: We see a hint that maybe seeing the Others as inherently evil may just be an opinion. Perhaps this Night's King saw more in the Others than everyone else seemed to see, and found their existence worth defending. To put it in perspective, everyone used to think the wildlings were inherently evil, but Jon has enlightened us a bit. This reinforces my idea that they are just another side of the coin of the CotF.
[Added 2/17/12] Craster's sons: Craster gives his sons to the Others. His wives warn Sam that Craster's sons are coming. This seems to imply that his sons are now Others, or at least wights. It could be that these sons are taken and taught the power of warging the dead as well as been introduced to whatever ice magic the Others may infuse themselves with. I think the fact that the wights are all dead is enough to say the sons become Others. The dead do not grow, so the sons would remain babies as wights. But as Others, they can still grow.
[Added 2/21/12] Coldhands: He seems to be a wight that can talk (in an "ancient language") and is working for Bloodraven and/or the Children. He rides a great elk, like the Children were said to do. He cannot pass through the Black Gate under the Wall. Also, Bran recalls "The ranger studied his hands as if he had never noticed them before." (Thanks Valyrian Breakdancing for that addition.) All signs show to him being a wight used by the side of the CotF. Now how would the Children have an ability to control a wight like the Others do? I think Bloodraven takes the "whatever means necessary" (that was his reputation in D&E) attitude and wargs a dead black brother (whose identity may or may not be significant), breaking the boundaries that the CotF always found necessary. I think this only links the similarities between the Others and the CotF.
[Added 7/3/12] Whitetree: When investigating wildling villages, at Whitetree the Old Bear said:
Note that I am always open to ideas and, though I defend my theories, I am not blind and know that there is certainly a chance that I could be wrong. That is why you will see my theories take a surer shape as discussions and time pass. This is a building block for us to try to discover the truth with what information we have.
Edited by The Shadow Fox, 12 July 2012 - 05:54 PM.