But winamp theming rested not only on the code allowing arbitrary bitmaps, it also rested on a user interface requiring zero discoverability. At some point people just knew where to click. In hindsight it appears almost surprising that there wasn't a fashion of black on black winamp skins (or maybe I just missed it)

Hah, that's a good point. When I think of it, the first Android skins, like HTC Sense (~3.0), were quite customizable. Every widget had a few stylistic variants, and I think you could even change the look of many components in the OS. Windows was very customizable until around Vista, too. I suppose people don't buy products for their theming features anymore.