I have a Label and I switch styles with Label.getStyleClass().remove("oldStyle") & getStyleClass().add("newStyle").
This works fine for the Label's text, the style changes as expected. (even if I just remove the old style and don't add a new one, the text is redisplayed with default color)
But if my oldStyle contains a icon defined with -fx-graphic, and the newStyle doesn't, the icon is still displayed. It is not removed.

Use the provided demo.
Select style errorMessage, press button setStyle, then select style infoMessage, then press button setStyle
Select style errorMessage, press button setStyle, then press button reset.

note: not sure about the version. It is the one that comes with jdk1.7.0_07