the hardest thing about problem solving/puzzles is you have to be as clever as an entire pack of role players so that they don't have too easy a time of it.
Anyway, some puzzles I remember from long ago:
a trap where a statue, make it pretty close to indestructable, breathes fire out as it turns in a circle. It activates as you get half way to it through the room, filling it with damaging elemental damage of your choice (don't have to make it fire if, say, you have a party full of protection against fire). (so the party, or lead member of it, is one-quarter across the room, the statue is in the center). It's a large room, and it takes 4 rounds to completely cross the room. Every other round, the statue breathes fire (or whatever else) doing just enough damage to make it dangerous (make saves difficult but not impossible, the point of this exercise is to drain party resources - like spells - if they don't act quickly, not kill them outright). They can't destroy the statue, they can't get through the room without getting smacked at least twice. But a fast character (like an unarmored barbarian in D&D) can make it to the only safe spot in the room without getting hurt-- the top of the statue. Where is the switch to turn off the mechanism? Inside the mouth of the statue where the fire is coming out. the solution is the fast character enters and races to the statue while everyone else waits behind. He climbs it and waits for it to shoot out fire again. He then reaches in and turns it off.
There's always the handy "chess" puzzle too, where you enter at one end of the board and have to move like the chess piece that would start in that square across the board (diagonally if a bishop, etc) or else some magic trap activates. Whatever will be effective against your group. That might be too easy though. So make it an unexpected variant: it's a checker board. Make some tough golems (immune to crits and more importantly, back stabbing rogue abilities) or something they can't beat two-on-one, and since they can't surround the enemy, they have to get around them. If it's checkers, they don't have to run, they can make an acrobatics or tumble check (or equivelant) to pass through the space, which neutralizes the golems for the remainder of hte time they're in there.
if you can find it, the old module "The Castle of Inverness," which was a tourney module in the early 80s, had a number of good traps in it, if I remember correctly. I have a copy, but it's in storage.
Come to think of it, if they're in a place that's typically of one element. Say, a fire giant stronghold, and they're prepared for whats coming (lots of protection from fire, etc), simply making some traps of a different type, like electricity or cold in this example, would throw them off. It makes sense to me. A fire giant king wants to keep potential rivals in his tribe out of certain areas or coffers, he'd trap it with something that'd hurt fire giants too. And he would be aware that interlopers would be prepared for heat and fire, so he'd have to do something against that too.
