click the part label. Then change the color.
Is the part label the little "tab" in the upper left corner, when you are in layout mode? if that's the case, then i have tried that, which didn't work...
The Part Label is in the lower left corner of the PART. At least it is on OS X. And . . . this does work.
The part should state what part type it is such as Header, Body, Footer, etc.
If using 11, then click the part and change the fill in the appearance tab of the inspector. If using earlier versions, right click it and change the fill there.