Yeah, they never sold well. Now then, why was that?
Well, as with uniforms, I believe it may be because they were overpriced. A costume change should be an impulse buy, something that makes you go 'ooh! That looks nice' and grabbing it before your wallet can start squealing.
Problem is that the ship skins:
A) came as a complete package with good parts and parts that made you go 'eew, no!'
B) in those packages probably cost too much for most to think about.
So, how do we fix that and get some more customization into ship costumes again?
A) Keep them as relatively minor and easy to implement changes. An hour or two of work to mod a venture or galaxy nacelle for an Ambassador, a tweaked sovereign saucer skin with many of the windows removed to simulate an up-armored ship, slightly different deflector geometries, that sort of thing. (To start with)
B) Separate the pieces and make them cheap enough to be an impulse-buy item. Or, say 25 to 75 Zen. Cheap enough to earn in a day or two of dilithium grinding. Too much, and a player will think before buying them, and too little and it won't be worth doing.
C) If you do go into a big modelling heavy piece (Avenger style nacelle for a ship custom-made for the class), don't be afraid to charge more than the average. In fact, other than keeping in a certain range, don't be afraid to vary the prices as needed to count for costs.
D) Ask players what tweaks they want. Find out what kind of slight changes, and try some things out. Ask around in the forums for ideas, what ships people want to customize more, and what they want to do to them. It can't hurt, and maybe they'll come up with some concept art for new ships while showing you what they want.
E) Seriously, missing a big revenue stream that could cut back the power creep for a while, cryptic.