The form TreeGraph[a, b] has two distinct interpretations according to the documentation. It is this ambiguity that causes you problems. Then the second argument b consists of all Labeled[], it is matched with the first definition on the documentation page, in which b is list of predecessors of the corresponding vertices in a. It is clear that this is the interpretation from the (unreported) error message you get.

The following method is probably both more robust and less convenient. We can manually strip the labels and apply them through options. This avoids the ambiguity above. Consider reporting it to Wolfram support. In my imagination, this is fixable, since your input has only one valid interpretation.

vertices = {Labeled[1, "Color?"], Labeled[2, "Size?"], 
   Labeled[3, "Shape?"], Labeled[4, "Size?"], 
   Labeled[5, "Watermelon"], Labeled[6, "Apple"], Labeled[7, "Grape"],
    Labeled[8, 
    "\!\(\*
    StyleBox[\"Size\",\nFontWeight->\"Bold\"]\)\!\(\*
StyleBox[\"?\",\nFontWeight->\"Plain\"]\)"],
   Labeled[9, "Banana"], 
   Labeled[10, "Apple"], Labeled[11, "Taste?"], Labeled[12, "Pomelo"],
    Labeled[13, "Lemon"], Labeled[14, "Cherry"], Labeled[15, "Grape"]};
edges = {Labeled[1 \[DirectedEdge] 2, "Green"], 
   Labeled[1 \[DirectedEdge] 3, "Yellow"], 
   Labeled[1 \[DirectedEdge] 4, "Red"], 
   Labeled[2 \[DirectedEdge] 5, "Big"], 
   Labeled[2 \[DirectedEdge] 6, "Middle"], 
   Labeled[2 \[DirectedEdge] 7, "Small"], 
   Labeled[3 \[DirectedEdge] 8, "Round"], 
   Labeled[3 \[DirectedEdge] 9, "Slimness"], 
   Labeled[4 \[DirectedEdge] 10, "Middle"], 
   Labeled[4 \[DirectedEdge] 11, "Small"], 
   Labeled[8 \[DirectedEdge] 12, "Big"], 
   Labeled[8 \[DirectedEdge] 13, "Small"], 
   Labeled[11 \[DirectedEdge] 14, "Sweet"], 
   Labeled[11 \[DirectedEdge] 15, "Sour"]};

getObject = Labeled[obj_, lbl_] :> obj;
getLabel = Labeled[obj_, lbl_] :> lbl;
TreeGraph[
 Replace[vertices, getObject, 1],
 Replace[edges, getObject, 1],
 VertexLabels -> Replace[vertices, getLabel, 1],
 EdgeLabels -> Replace[edges, getLabel, 1]]

In this case, since all vertices and edges are labeled, one can also use the following, simpler code:

TreeGraph[
 vertices[[All, 1]], edges[[All, 1]],
 VertexLabels -> vertices[[All, 2]], EdgeLabels -> edges[[All, 2]]
 ]

Hi Valeriu!

We were probably typing at the same time. :) I didn't see your response until now.

It seems that in the first case the second list is interpreted as a (non-correct) list of predecessors (see Documentation). As you give explicitly an edge in the second list, the second list is interpreted as a list of edges and all is ok. Why so? Is this a bug? I don't know!