ack... I hope this is not something you're trying to get professionally printed as MS Publisher is NOT a professional-level DTP app.
What you'd really want to do is to IMPORT the clipart (presuming it's a vector clipart) into Draw. Then you'd want to ungroup it, select the item in question you want to recolor and just change the color (just a matter of selecting the item and clicking on a color swatch).
Then regroup the items, save the file in case you have to re-do it again, and then EXPORT the file into the original format you imported from.