I dont know much about Kara-Tur, so looked up the wiki:en.wikipedia.org/wiki/Kara-Tur
Since Ninjas are a Japanese thing, either Wa or Kozakura seems to make the most sense.
I'd probably set it up like this: The Emperor is mostly a ceremonial position, but wishes to gain true power away from the shogun. To this end, the Emperor has hired the assassins guild to eliminate the shogun. The assassins guild sees an opportunity to become the true rulers as the power behind the throne by replaing his daughter with one of their own agents, your wife.
They kidnap/assassinate the emperor's daughter, and replace her with the changeling assassin. The assassin though, sees that the emperor is evil and sadisitc, and would be far worse then the Shogun, and that the assassins will not be able to control him as they suspect, so the assassin refuses to carry out her mission to eliminate the shogun, and give the emperor true power.
When she betrays them, the assassins guild tells the Emperor that the changeling was acting alone, and was attempting to assassinate /him/. The Emperor knows that the changeling has information that could implicate him in plotting to overthrow the shogun. So both the guild, and the emperor have reason to want to hunt the changeling down, and she'll have to evade agents from both. To avoid most of them, she's fled into the west where the likelyhood of running into imperial or guild agents is small...but you just never know.