On the labels tab in your layer properties, when you choose to define classes of features and label them differently, you get the new drop down and the radio button to allow you to choose to make these labels visible or not. PLEASE add another radio button that would allow you to choose that this labeling can be automatically added to the legend.
This would be an incredible time saver, and one of the only current workarounds is to add this layer again, choose symbology and redo your labels/symbols so that the layer doesnt show up in the map but the legend shows for the class of features you just labelled in you other layer. Seems like it wouldnt take too much to write that in with the label engine code to the maplex and standard label engine would look for a call out under the labelled classes of features. I have had many maps eat up precuious hours playing with label and legend matchups. Norm....Bryan Co Ga.