Most people will complain that they are too easy, but if you make one too hard, a large percentage of your audience will simply quit the game. The best puzzles to me are puzzles where you have to arrange things in an order, and you find that order by experimenting. In a puzzle platformer you can use switches, transports, and keys mainly. The hard part is really making them feel unique. For that, you have to throw in things that aren't normally used. Maybe a monster has to do something to help solve the puzzle. The other hard thing is you really have to finish the game before you have it tested, because once someone solves a puzzle it's basically over, and you will run out of game testers very fast. You can also probably add conversations with characters that might give hints, etc. It's the type of audience that has more patience for exploration and story. What I've found is I develop an interesting setting, maybe a spooky graveyard or something, and then ideas for puzzles start coming to me. If I try to develop the puzzle outside the setting, it's a lot harder.
