Hi Raine,
I found this note in the specs itself:
http://earth.google.com/kml/kml_tags_21.html#style
...but deprecated does not mean that it is not supported anymore. Strange, but changing the header version from 2.0 to 2.1 fixes this issue and the icons are re-apprearing...