I've changed the icon (the star) for the start menu, but I'm stuck with the purple background color as my new icon is transparent. How do I change the color?

I guess I could just change the icon background from transparent to whatever color I'd like, but what if I want to do it the hard way?