HoMM IV and 12 Kingdoms share more than that one track though, for example
http://www.youtube.com/watch?v=5I7ufyaEGK8
&
http://www.youtube.com/watch?v=XbJ1oxPvZrY
Are not as identical as the last pair, but the similiarity is obvious. And there are more, too. The Order theme of HoMM IV for example.
Now, Heroes and the first episode of Twelve Kingdoms were published almost at the same time, with only several days inbetween (Heroes being the first). Digging the intarwebz has revealed that the music in the anime has most likely been inspired by several different relatively modern sources, whereas Heroes IV's music has its roots in at least Irish folk music. A theme similiar to the one I linked in this post has been used elsewhere as well.
So I think it's fair to presume that one of the inspirations for the music in Twelve Kingdoms was Heroes IV, simply because they use so many nigh-identical tracks. Perhaps they made a deal of some sort. Or perhaps they simply used an identical source. Some detective story this turned out to be!
The full story, it seems, will forever be hidden in the mists of time...
...
Oh yeah, these were the FFH forums! Erm... well, compliments about the soundtrack! Really good choices, regardless of the original source.