The seed of the idea that eventually turned into that first novel and finally matured into Chosen of Azara was an image that came into my mind one day, of a highborn young woman alone in the woods, seeing a vision of an unknown man, and then some time later, the man appears, in the flesh, at the door of her home, looking for her.
The earlier story starts with that scene and goes on with the adventure from there. I also discovered that the first story also has a magical talisman that the young woman wears as a necklace, two brothers, a dubious fiance, a lost kingdom, and a king who under normal circumstances should be waaaaay past his "for best quality, use by" date. And, like Chosen of Azara, it's also set in the world of Estelend which I had begun developing probably about the same time or a little earlier.
A lot of writers, especially newer ones, worry that just because one story has the same starting premise and even some more specific plot elements in common with another story, that that makes the two stories the same. You see this on the NaNoWriMo boards a lot - "Am I plagiarizing [movie or book] by having [incredibly broad and common story element] in my story?" (Someone wanted to know if they were plagiarizing George R.R. Martin by including sex in their fantasy novel.) Or, "This movie stole my plot!" Young wizards going to wizard school (A Wizard of Earthsea, anyone?) or characters who are half-human, half-god (a substantial chunk of Greek mythology) seem to cause particular concern.
The answer is, No, you're not plagiarizing, No one stole your idea, There are no ideas that have absolutely never been done before. Two writers can start out with remarkably similar premises, and even some specific plot elements, and end up with very different stories.
And, in fact, the SAME author can write two very different stories from the same starting point and with the same plot elements.
The original "girl sees strange man in a vision in the forest" story is pretty straightforward. Girl sees vision, dude shows up, girl (accompanied by brothers and dubious fiance) goes off on adventure with mystery dude, lost kingdom, yada yada, (eventual) happy ending.
I wasn't real happy with how that story came out, and in fact the girl got a name and personality change halfway through. She started out as kind of this pathetic spinster would-be-hermit, and eventually eveolved into someone more like the character of Lucie turned out to be. Aside from the main character, the story as a whole didn't do what I wanted it to do, and it certainly didn't do justice to my original idea of the man in the vision.
So I turned my mind (aka the Idea-o-Tron (TM)) to learning more about the guy in the visions. Ancient king, lost kingdom... How in the world is he showing up in visions in the woods right here, right now, to this particular young lady? I started digging more into that, and that was where Sevry and his story (and the very cool time travel technique) came from. But there was more to it than that; how did the war begin, that destroyed Sevry's kingdom? Kingdom-annihilating wars don't just come out of nowhere. So that led deeper into Savaru's history, and to the story of Juzeva.
By the time I'd worked out all this backstory, I realized it wasn't just backstory; the stories of Juzeva and Sevry were too closely connected to Lucie's story, and had too much important information, and were too compelling to me to just be relegated to backstory, to be worked in small chunks into the story of Lucie's adventure. So the new version of the novel started with Juzeva and became an inter-generational tale of the fall and restoration of the kingdom of Savaru. And it turned into a novel that I decided I loved, and was proud to publish (as opposed to the original version, which will remain in the privacy of my hard drive; though I'll never delete it because you never know when something from an old story can be recycled into a new one.)