As stated, this is for when your PCs are starting to getting in to the habit of killing everything they come across that looks vaguely evil.
A king hires the party to go as an embassy to a powerful semi-barbaric tribe on his border. He sends them with gifts to the tribe and an offer of peace: he is hoping to secure this border in preparation for a campaign elsewhere, and would like a temporary cessation of the intermittent raids across his border.
A little way in to the tribe’s territory, the PCs are attacked by a small number of warriors, clearly, from the tribe. Assuming your PCs aren’t intelligent, they slaughter them with ease and loot the bodies. They then merrily proceed further in to the tribal territories to where the leaders are.
Of course, your PCs might be intelligent. In this case the plot will turn in to the problem of how the PCs defend themselves against people trying to kill them without killing the attackers (this shouldn’t be too hard: the attackers are fairly inept (though the PCs won’t know this at first) and will surrender if a couple of them take bad wounds). This will then be followed by a diplomacy mission - which you can make as simple or complicated as you like.
What happens next.
A little bit later, the PCs are met by the chief and a large number of warriors (too many to fight). It transpires that the people who attacked the PCs were a group of youths who had only recently gained adult status in the tribe, who were out on a raiding party (raiding is a way of life in the culture and is how they gain honour). The rest of the tribe is understandably not too pleased that their youngsters have just been slaughtered.
This not only will seriously jeopardise the original mission, but will also put the PCs at the mercy of the tribe and in serious danger of their own lives. Even the best diplomacy in the world will not let them get away without serious reparations (perhaps in paying blood money or by performing some service to the tribe). On the other hand, if they choose not to do this (or are inept at diplomacy), they may choose to escape and make a bid for freedom.
If they succeed (I leave the details of the difficulties to you), they will face a further problem. The king who hired them will be rather unhappy at the failure of their mission and the way in which they have angered the tribe. The obvious way in which he can placate them and prevent a series of retaliatory raids is to catch and hand over to them the miscreants they are demanding.