Answering my own post here, in case others wonder about the same thing.
This post from Sergey put me on the right track: http://tech.groups.yahoo.com/group/kicad-users/message/6399 But what I still missed was how to change the actual color of the new material. Well the answer was hidden in plain sight. Kind of. I just had to click that "color square" which appears to the right of the Diffuse slider (and/or possible Ambient, Specular or Emission, if applicable, but I used diffusion).
