Azthor I believe you're referring to the Ztah steppes/plains/what have you. Its not really desert persay, but sort of a light grassland. At least thats how I recall it.
Its rather a distance from where we're playing, which is up by Ligoria, in the Storm Coast. Perhaps you'd like to pick something a bit closer to there.
Close yet not quite, I had in mind south/west of that a the idea was to use a literally unnamed region to add a bit of a foreign style (that is, in case in case is allowed, of course). Alas now that you mention it, using the steppes as an origin would be reminiscent of the Mongol Hordes, which is also mighty fine for a Warlord. All the same, I'd inevitably start out closer to whenever you are, something which you've already helped me with as I didn't have much of an idea of which area was most populated by players.
I think the isolation is the reason he's playing all the way in Ztah. Course a Ztah warband/tribe/hoard could turn up in the Storm Coast...Like being captured by slavers?
Good ideas and fitting should I wind up with the Warlord styled character, the other option'd also require a relatively uncharted location as he is supposed to be unknown in Elbreth and having been a powerful magic-user in a low-fantasy setting would inevitably result in considerable renown in spite of having been crippled to the point of uselessness. One is a military leader and the other is "social player", neither being known nor capable of using magic, although the later'd have quite a load of knowledge regarding the topic.