Some puzzles make for great programming exercises, but because they are, they are not so good for games, because everyone's seen them before.
That's not to say that you can't have a fresh turn on, say, the wolf/goat/cabbage puzzle. http://ifdb.tads.org/viewgame?id=mziqfn78iaytu5uf is an example of such a game with humor in it. But it needs to be wrapped up in something original.
Konigsburg Bridge/graph theory puzzles are another example, e.g. visit all rooms without visiting any one twice, or go through all passages between rooms once. However, if instead of having just bridges, you could have obnoxious NPCs and you were only able to erase 3 of them, you could have a neat puzzle there.
The puzzle where you make 4 gallons from a 5- and 3-gallon jug is also one that's seen before, though Tea Ceremony did well at the 2014 IFComp.
Time travel puzzles have been done before, but all the same, there are so many ways to do them that you'll often have a new take. For instance, Fifteen Minutes from the 2014 IFComp fits the bill and adds humor, etc.
Mazes, especially ones where you can't leave items, and reciprocal directions don't lead you back where you started, are a big risk. But it can be fun to find ways to subvert them.
Also standard logic puzzles such as the truth-teller and the liar can possibly grow stale. You want the puzzle to be more than "have you seen this before?" The twist of having a third sometimes-liar also might be a bit stale, but maybe if you had more liars or truth tellers, or you had everyone look at an item or something, you could have a good puzzle.
Other things like a sokoban-style puzzle are probably more fun to program than to play, and they're probably better off in non-textual environments.
Anything that requires too much scratch paper without ingenuity is very risky. But it can be done! Anything that adds a story can go a long way.