sometimes they change stuff, and if you've got the 'old' version or some sort of combination of elements that is not longer allowed it's declared "invalid"- they don't take it away, but you can't change that particular costume without losing it.
One of my oldest characters has pants with the Malaise pattern which was removed from the costume creator- he's still got the pants, but I can't change that costume without losing the pattern.
The Nethergoat Archive: all my memories, all my characters, all my thoughts on CoH...eventually.
My City Was Gone
I think a few people (or more than a few) were able to get multiple back items such as wings and a trenchcoat or multiple cape-like items onto a character due to a bug. I know they've been trying to "clean" those up.
Father Xmas - Level 50 Ice/Ice Tanker - Victory
$725 and $1350 parts lists --- My guide to computer components
Tempus unum hominem manet
Depending on how old the costumes are, the face and face with masks categories were merged together. So any old, masked costume would show up as invalid and the head would change.
Sometimes a combination of costume pieces is no longer valid, but sometimes you also get that message because stuff has just been shuffled around in the editor interface, so your old costume is still possible, you just have to find where the pieces are.
Wow! Thanks everyone for those timely and concise explanations. It is good to be back. 
"This rooster has a beak! A beak that calls out Death-a-Doodle-Do!" - Mr. Burns
Ok I'm back after a hiatus and I have a question that I cannot find an answer to using the search function.
I have several characters whose costumes are marked with a padlock. If I try to change these costumes it says the costumes have invalid pieces and the pieces will, uh, go away if I try to change the costume.
What gives? What is this all about? I haven't tried to hack any costume pieces. All I did was go away and then return. Is this my punishment *sob* :'(
"This rooster has a beak! A beak that calls out Death-a-Doodle-Do!" - Mr. Burns