Exactly what you said, this solution doesn't make super-hard puzzles, it makes not-fun puzzles. The obvious next step that I would challenge you to do would be to optimizes for puzzle cuts so that they do not follow the main color lines of the image as much as possible. This would result in pieces that are just as interesting, but produce puzzles that are radically more fun to actually put together.

A good puzzle will not bore the player. Boring is that there are many blue pieces that all look exactly alike. Trying each one over and over is not fun. But with a tweak to your technique you could make sure that every blue piece that can contain another color would, thus increasing the variance of unique pieces which is not boring for players. Finding a blue piece with this little bit of brown and a spec of purple means the player can get to remember that and hunt for where it could go which is the fun part of puzzles. Do that and you can approach puzzle companies to license them a tool to make more fun puzzles and they will buy it.

Now of course your tool can't solve everything you can still end up with rubbish like: http://www.amazon.com/USAopoly-M-Ms-Puzzlemania-Puzzle/dp/B0...

And in contrast a really good puzzle that at first glance looks like it is all one color, but filled with so much detail it is a blast to put together. http://www.amazon.com/Ravensburger-78000-Fire-Dragon/dp/B000...