This is a common problem GMs struggle with at first: Why characters from such different clans would ever work with each other.
The easiest way to solve this problem is to have all the players work for imperials, who are theoretically neutral. Many games have the players acting as Yoriki to the Emerald or Even Jade magistrates, or have them working for some other imperial organisation such as the legion.
However, the only thing you really need to consider when forming a party of characters is to determine who they work for and why. Just remember that it is perfectly fine for a samurai of one clan to work for a lord of another. High ranking samurai tend to trade vessels like pokemon for a variety of reasons. Maybe a lord owes another a favor, or there is some sort of exchange program going on where clans trade samurai to learn from each other, Maybe s samurai is for all intents and purposes a political prisoner and must cooperate or face consequences worse than death, or perhaps the lord is simply dealing with an issue that is such a threat that other lords have "donated" a few bodies to protect their own interests or just to say that they helped. Even Samurai from clans that are currently at war with each other can find pocket cases where a samurai is allowed to work for a rival lord. That samurai would be met with the bare minimum amount of respect (if that) and and transgression would be punished MUCH more harshly, but it is still in the realm of possibility. In fact, working with your Gm and finding out why your character is working for this particular lord is a great way to delve into your character backstory and find their unique mark on the setting.
Also, it is even possible for Samurai to come together and go on a quest independent of their lords. Maybe they are all good friends and have need to do something that is important or known to only them. However, aside from immediate emergencies it will be hard to justify to ones lord why they are repeatedly acting independently, often in life threatening situations. This type of scenario is better suited for shorter campaigns and one shots. That said, samurai fresh from their gempuku often take a year or so to do a walk about the empire and get into all sorts of adventures that do not require oversight from their superiors.
Bottom line, there are for more reasons (interesting ones too) to figure out why samurai from different clans WOULD work together rather than why they wouldn't. Just focus on their unifying factor and everything else should fall into place.