We appreciate all the reports of this rare bug. It was never enough to reproduce directly, but we believe we have found and fixed this issue:

Styles are uniquely identified by base url + id, e.g.,

c:/myfile/foo.kml#myredstyle

Two different kml/kmz files may safely have differing styles with the same id
until placemarks referencing the differing styles are saved to the same file. In
this case there is a collision on the style id and only 1 of the styles is
written, causing one or more placemarks to utilize an incorrect style.

This situation is trivially reproduced by hand but is rare when just using the
GE client for editing data. In particular one must choose the "share style"
option for a folder, then save that folder in a kml/kmz file different from the
one it came from.

Possible sequence of events:

1. open foo.kml
2. edit a folder from foo.kml and select "share style"
3. move the folder into My Places
4. save My Places