Mordechai who was from tribe of Binyamin is called a Yehudi. A member of Yehuda. so this seems a contradiction but the Gemara tells us that anyone who rejects idolatry merits being called a Yehudi. So too it was with Chanaya, Mishael and Azaryah (who in one view in the Gemara were not from Yehuda).
Why specifically Yehuda? Malchut Yehuda did not sink into idolatry when Malchut Yisrael did. The same Gemara that discusses this in Sotah also discusses Yehuda and Tamar. It tells us that Yehuda merited to have two letters of Hashem's name added to his own (from birth as a prophecy) because he repented in public by declaring that Tamar spoke the truth and thus sanctifying Hashem's name. While Yosef received only one letter because he only restrained himself in private.
Mordechai and Chanaya, Mishael and Azaryah all rejected idolatry in public and risked their lives for it-- while in exile. In doing so they helped pave the way for the first exile. For Yisrael or Yosef to become Yehudim-- it would take a public repentance and a public stance against idolatry. The return of the other tribes who have sunk into idolatry requires that they become Yehudim through public repentance and the rejection and abandonment of idolatry.
David HaMelech was fated to descend from Yehuda's repentance. The public repentance of the remaining tribes and their transformation from Yisrael to Yehudim brings the coming of David HaMelech's descendant, Moshiach. The missing 'Hey' of Yosef or Yisrael remains the failure to recognize Hashem.
The Gemara tells us that Tamar's call to Yehuda 'Haker' recognize is not merely to recognize who the items belong to but recognize who saw what he did and who sees all things, namely Hashem. Yehuda had gone down from his brothers after the sale of Yosef, intermarried, produced unworthy children and finally degraded himself by descending to a prostitute, an alien woman. Much as his descendants David Hamelech and Shlomo Hamelech would do after him. Public repentance redeemed Yehuda and David Hamelech. Through repentance, the house of Yehuda and the house of David was rebuilt. The final redemption requires transforming the house of Yisrael into the house of Yehuda and the transformation of Yisrael into Yehuda to restore Malchut David. That can only be done through public repentance. For Yisrael to recognize G-d and reject idolatry. Only then can Israel be redeemed.