1. The straightforward answer to your question is as follows.

One sees from the Gemara in Eruvin (46b) that the rule of "Halachah k'Rav Yosef me'Chaveirav" is not so simple. Immediately after the Gemara states this principle, it asks how far it extends. Does it mean that one may rule for the public on the basis of this principle, since the Halachah clearly follows Rebbi Yosi (this is the view of Rebbi Asi), or does it mean that it is likely (but not absolutely certain) that the Halachah follows Rebbi Yosi even when many others disagree with him, and therefore one may instruct an individual to act according to Rebbi Yosi's opinion, but one may not teach in a public lecture that the Halachah follows Rebbi Yosi (this is the opinion of Rebbi Chiya bar Aba; see Rashi DH Matin)? The third opinion (that of Rebbi Yosi b'Rebbi Chanina; see Rashi DH Nir'in) is that one may not instruct an individual to do like Rebbi Yosi if the majority of Rabanan disagree with him, but if someone did follow Rebbi Yosi, we do not say that what he did was invalid and that he must do it again.

Therefore, according to the opinions of Rebbi Chiya bar Aba and Rebbi Yosi b'Rebbi Chanina, it was necesary for Rav Yehudah Amar Shmuel (in Bava Basra 25b) to teach that the Halachah follows Rebbi Yosi; that is, the Halachah is clearly like Rebbi Yosi in this case, even according to the opinions in Eruvin that the Halachah is not always clearly like Rebbi Yosi. Therefore, one may teach in public that in the case discussed in Bava Basra, the Halachah follows Rebbi Yosi.

2. I found an interesting Gemara which may shed more light on the opinon of Rav Yehudah in the name of Shmuel, concerning whether or not we always rule like Rabbi Yosi even against the majority. The Gemara in Yevamos (67a) discusses a dispute between Rebbi Yosi and the Chachamim in the Mishnah. The Gemara says, "Amar Rav Yehudah Amar Shmuel: these are the words of Rebbi Yosi, but the Chachamim say...." The Rosh there writes that the Halachah does not follow Rebbi Yosi because he is a "Yechida'ah," a minority opinion, and the Rabanan disagree with him. One sees from the fact that Rav Yehudah Amar Shmuel said that the Chachamim disagree with Rebbi Yosi that this means that their intention is that the Halachah follows the Chachamim. Now we can understand better why in Bava Basra Rav Yehudah Amar Shmuel needs to say explicitly that the Halachah follows Rebbi Yosi (as this cannot be assumed automatically).

3. The original question still remains: How can Rav Yehudah Amar Shmuel go against the rule in Eruvin which states that the Halachah follows Rebbi Yosi even against the majority? The answer to this may be foudn in Tosfos in Eruvin (46b, DH k'Rebbi) who points out that the rule of "Halachah k'Rebbi Yosi me'Chaveirav" seems to be contradicted by the Gemara later (47a) which states that according to Rebbi Yosi, a woman may become betrothed (with "Erusin") to a second man immediately after being divorced from her first husband. Rebbi Yochanan states that the Halachah follows Rebbi Yosi. The Gemara comments that this implies that the opinion cited earlier, that such a woman must wait three months, must be a minority opinion. The difficulty is clear: If there is rule that "Halachah k'Rebbi Yosi me'Chaveirav," and even if the Rabim disagreed with Rebbi Yosi we still would rule like him, then why does the Gemara say that we rule like Rebbi Yosi only because it is an individual, and not the majority, who argues with him?

To answer this question, Tosfos says that the Gemara there (47a) follows the view of Rebbi Yakov bar Idi. This means that the view of Rebbi Yakov and Rebbi Zereika, who stated (46b) that "Halachah k'Rebbi Yosi me'Chaveirav," is disputed by Rebbi Yakov bar Idi (who came after them). This is evident from the fact that Rebbi Yakov bar Idi says that the Halachah follows Rebbi Yosi when he argues with Rebbi Yehudah, and the Halachah follows Rebbi Yosi when he argues with Rebbi Meir, which suggests that the Halachah follows Rebbi Yosi only when he argues with an individual, but not when he argues with the majority. This proves that Rebbi Yakov bar Idi does not agree with the rule stated by Rebbi Yakov and Rebbi Zereika.

4. Tosfos in another place writes that the Halachah does not follow Rebbi Yosi against the majority, but only against an individual. Tosfos later in Eruvin (83b, DH Shiv'as) writes that when the Rabim disagree with Rebbi Yosi, the Halachah does not follow Rebbi Yosi.

5. Accordingly, we may say that Rav Yehudah Amar Shmuel in Yevamos (67a) agrees with Rebbi Yakov bar Idi and does not agree with the rule of "Halachah k'Rebbi Yosi me'Chaveirav." This is why Rav Yehudah Amar Shmuel says that since the Chachamim disagree with Rebbi Yosi the Halachah follows the Chachamim, and this is also why it was necessary for him to say in Bava Basra (25b) that the Halachah follows Rebbi Yosi.

Kol Tuv,

Dovid Bloom

Here is a different answer to your question from Eruvin 46b. This answer is based on another Gemara in Eruvin, at the beginning of 27a. The Gemara there presents a very important principle in the name of Rabbi Yochanan: "Ein Lemedin Min ha'Klalos" -- the rules for determing the Halachah are not absolutely applicable. Therefore, even though there is a general rule that the Halachah follows Rabbi Yosi against his colleagues, there are exceptions to the rule, and this is why Rav Yehudah in the name of Shmuel had to rule (Bava Basra 25b) that the Halachah there follows Rebbi Yosi; this was in order to ensure that we know that the case in Bava Basra is not one of the exceptions to the rule.

I have found sources to support the idea that the principle of "Ein Lemedin Min ha'Klalos" applies even to the rules that Chazal gave concerning how to rule in disputes between Tana'im.[This is not so apparent from the Gemaras, because none of the places in Shas where "Ein Lemedin Min ha'Klalos" is mentioned refers to principles about how to rule.)

1. The first source is the Rashba (Teshuvos 1:40). The Rashba refers to the Gemara in Avodah Zarah (32b) which discusses the words of Raban Shimon ben Gamliel in the Mishnah there (29b). The Gemara cites "Rav Yosef Amar Rav Yehudah Amar Shmuel" who says that the Halachah follows Raban Shimon ben Gamliel. The Rashba was asked: Why is it necessary for Rav Yosef to rule like Raban Shimon ben Gamliel when a common principle (see, for example, Kesuvos 77a) states that wherever Raban Shimon ben Gamliel is mentioned in the Mishnah, the Halachah follows his opinion, with the exception of three cases (and the Mishnah in Avodah Zarah is not one of them)?

The Rashba answers that "Ein Lemedin Min ha'Klalos" applies even where the Gemara states "Chutz" -- "with the exception of" (as is the case here, because the Gemara in Kesuvos (77a) states that the Halachah always follows Raban Shimon ben Gamliel with the exception of three cases.) Even though one might have thought that the rule is reliable since the Gemara says that there are three exceptions -- implying that there are no more than three, the rule still does not always apply. The Rashba writes that the Halachah follows Raban Shimon ben Gamliel where there is proof for his opinion, or where his reasoning seems probable.

Accordingly, the Rashba's words are proof that "Ein Lemedin Min ha'Klalos" applies even where Chazal seem to provide us with a clear guideline about how to rule.

2. Another source is the Gemara in Bava Metzia (69b), where Raban Shimon ben Gamliel is cited in the Mishnah. The Nimukei Yosef (40b of the pages of the Rif) cites the Rif and the Rambam who write that the Halachah does not follow Raban Shimon ben Gamliel. The Nimukei Yosef writes that even though the rule is that the Halachah always follows Raban Shimon ben Gamliel in the Mishnah, the commentaries explained in many cases similar to this one that "Ein Lemedin Min ha'Klalos." The Nimukei Yosef seems to be referring generally to guidelines in Chazal concerning how to rule, and not only to guidelines concerning Raban Shimon ben Gamliel. Accordingly, we see that the commentaries often write that the way of ruling does not always follow the general guidelines.

3. Finally, the Kesef Mishneh (Hilchos Erchin 1:6) writes more explicitly about the principles mentioned in Eruvin (46b). He writes that the rule that "in a dispute between Rebbi Meir and Rebbi Yehudah, the Halachah follows Rebbi Yehudah" is merely a general rule and "Ein Lemedin Min ha'Klalos." Therefore, if there is a good reason to do so, it is possible to rule like Rebbi Meir. Again, we see that "Ein Lemedin Min ha'Klalos" applies even to principles clearly stated in the Gemara.

Kol Tuv,

Dovid Bloom