I was just looking at the insert header options and noticed that most of them are inserting tables into your header. In that case, you can right click in the space where you want the color to change, select borders and shading, select shading, pick a fill color, pick a style if you like, and select whether you want your changes to apply to the one cell or the whole table at the bottom. That bottom selector defaults to change the whole table, so watch that one.

If you're header has an image in it, and you want to change the colors, Word 2007 has some fun options for that as well, so post back for other ideas.