Why is he a barbarian, anyway? I assume since he was a king or whatever that he was at least a little civilized. Maybe not you, but when I think of barbarians, I don't think of kingdoms with walls, if they even have a kingdom. Go to Comment
The player characters, experienced and somewhat well known, hear rumors and travelers' tales about a distant area being overrun by dragons (or other terrifying monstrosities). The locals have sent them a message, begging for heroic aid.
When they investigate, they discover that nothing of the sort is going on. It turns out that a group of thieves wanted them out of the way so that they could rob them (or someone who would normally receive their protection).