(Note: this is a preliminary skim of the subject. For the full account, after research, see this entry.)
This will make more sense later, after I post an actual review of Shounen Onmyouji, which everyone, incidentally, should go watch. Right now.
For now, though, research results and links (which may help for YnM, too).
The Juuni Shinshou (Twelve Heavenly Generals) are Buddhist and come to Japan from India via China. They are, variously, known as yaksha (nature spirits), devas (warrior spirits/gods-of-a-minor-sort), and tenbu (Japanese take on Devas). They are initially associated with Yakushi Nyorai, the Medicine Buddha, and healing.
However, twelve being a popular number in Buddhism, they have become associated and overlapped with the twelve cycles of time (hours of the day, years in a cycle, etc.) and the twelve animals associated therewith. These are the animals commonly known in the West as the Chinese zodiac (see also Fruits Basket). (Maybe. See eta.)
Because the animals have elemental associations from the Taoist system (which is different from the Buddhist elements but quite similar to Shinto, oh god don’t get me started on the elements), the twelve generals have picked up elemental associations to go with their animal associations.
Important! These associations are variable! There are several variations on which animals go with which generals. Which elements go with which animals varies on a larger cycle of years as well as each having a fixed element and a base association with yin or yang, and, when filtered through the creative license of anime/manga, the whole thing gets… complicated.
In any case, it appears that the zodiac filter is how the yaksha Sanchira, for example, becomes the Serpent of Destructive Fire. Certainly the personalities given to the characters in both SO and YnM have some good matches with the zodiac personality readings.
Where the particular names come from, apart from the elemental constellation names given to the strongest animal in each element (Dragon becomes Seiryuu, Horse becomes Suzaku, etc.), I’m still trying to figure out. Similarly how the notion was arrived at that Abe no Seimei’s generic plethora of shikigami should correlate with the Juuni Shinshou in particular. I have, as yet, found no source explaining that that is not clearly contaminated.
ETA: I have also come across some indications that the twelve guardians of the Medicine Buddha and the twelve elemental/time figures are, in fact, separate groups that have been confused because of the similar translation of their titles: 神 in the first place and 天 in the second, so that it might be more precise to say the Twelve Divine Generals and the Twelve Heavenly Generals, respectively. Results of this line of inquiry will appear in a later post, if it comes to anything.