While this is a complex topic, here are the major details:
Can a mitzvah be called fulfilled even if it is built on an averah?
No
A stolen Lulav is invalid on the second day of Sukkot. The reason given on sukkah 30A is:
משום דהוה ליה מצוה הבאה בעבירה שנאמר (מלאכי א, יג) והבאתם גזול ואת הפסח ואת החולה גזול דומיא דפסח מה פסח לית ליה תקנתא אף גזול לית ליה תקנתא לא שנא לפני יאוש ולא שנא לאחר יאוש
It is unfit because it is a mitzva that comes to be fulfilled by means of a transgression, which renders the mitzva unfulfilled, as it is stated: “And you have brought that which was stolen and the lame, and the sick; that is how you bring the offering; should I accept this of your hand? says the Lord” (Malachi 1:13). Based on the juxtaposition in the verse, it is derived that the legal status of a stolen animal is equivalent to that of a lame animal. Just as a lame animal, because it is blemished, has no remedy and is unfit for use, so too, a stolen animal has no remedy. There is no difference before the owners reach a state of despair of recovering the stolen animal, and there is no difference after despair. In both cases there is no remedy.
While the talmud cites another opinion, this is the accepted one.
The Mishnah Sukkah 2:3 says that if one builds a sukkah on top of a camel or a tree, it is valid, but one may not use it during yom tov (but may during chol ha-moed). Rashi adds that if one uses it on yom tov anyway, he has nevertheless fulfilled the mitzvah of sukkah.
This is not a case of Mitzvah Habaah Biaveirah, but a classic example of something which is invalid Lechatchila but ok Bdieved. The Rabbis forbade climbing a tree or riding an animal because one might come to break a branch, either while climbing or to hit the animal with. However, they did not invalidate the Mitzvah of Sukkah if it was done in this method. This is quite different from the case of using a stolen Lulav.
The Tosafists make distinctions between different kinds of Mitzvot acomplished through an Aveirah (3 if my memory serves), but I believe that is beyond the scope of this answer.