Well, i think the sequel has to follow on the shoes right, you gotta have a badass looking character, and make it still about this agile character, that plays outside the law, is an assassin, uses social stealth.
So europe could work, but they would have to rip off Thief. They could do it anyway, i would be all for it. Japan could work too, either get this samurai type of dude going on, or ninja most likely.
It could also happen that you will travel not to one culture but to more than one, the Kingdom while beautiful to just walk across on your horse, was pretty much put aside midway through the game, so they could do cities in different time periods and places, which would mix nicely with a possible "near future" city that is placed in the time of our hero.
We'll see, there's soo many possibilities, it's awesome.