1) The Beis Yosef (by Rav Yosef Karo) writes in Hilchos Shabbos 314:5 (paragraph beginning "veha'Rav ha'Magid") that Rav Yehudah broke the branches because he wanted to enjoy the good smell inside the tree. This is permitted in a similar way that the Gemara here cites the Mishnah in Maseches Shabbos 146a, that one may break a barrel on Shabbos in order to eat the dried figs inside the barrel. There is no prohibition of Muktzeh if one breaks the wood in order to reach food or a pleasant smelling item. In contrast, the Gemara in Beitzah 33a which states that wood may be used only for heating is discussing using wood as a support, which is forbidden.

2) I think it may be worthwhile to look at how one of the Mefarshim on the Sugya summarizes the Halachos about different kinds of wood.

The Rosh (Rabeinu Asher), in the fourth chapter of Beitzah, paragraph 12, writes that one may not lean the pot on the log "she'Lo Nitnu Etzim Ela l'Hasakah." Later, in paragraph 14, he writes, "It is permitted to move 'Atzei Besamim' in order to smell them... and to break them in order to smell them." "Atzei Besamim" are woods of spices. These are different from the wood that the Rosh mentioned in pargaraph 12 because they contain within them aromatic properties.

3) The Rosh continues and writes that this is not different from the Mishnah which states that one may break open a barrel in order to eat the dried figs inside.

We learn from the Rosh that one may move wood in order to obtain food or a good smell.

4) In fact, we may learn from the Halachah of "Lo Nitnu Etzim Ela l'Hasakah" that for "Hasakah," heating, one is allowed to use wood on Yom Tov. This indeed is stated by the Shulchan Aruch (Orach Chayim 511:1): "One is allowed on Yom Tov to make a bonfire to keep warm." The Mishnah Berurah there writes that even though the Torah states only that one may do certain forms of work on Yom Tov for food preparation, there is a Halachah (see Beitzah 12a) that "once Melachah was permitted for food, it was also permitted even if not for food."

5) Therefore, in the same way that one is allowed to use wood for making a fire, Rav Yehudah used the wood to create a pleasant smell.

Kol Tuv,

Dovid Bloom