A difficult one which I found very enjoyable was the following:
A group of people are gathered together to play a game. The rules are explained to them as follows. They will each be given a hat with a positive number on it. It may be any positive number, not necessarily an integer and they will not necessarily be sequential.
Everybody will be allowed to see everybody else's hat, but not their own. At this stage, there is no communication allowed, even implicitly (for example, standing next to the person with the largest number you can see would be disallowed). If this is a sticking point, the problem can be modified so that the players are given their hats separately and only shown photographs of each other player with their hat, so that they are never in communication while wearing that hats.
Once everybody knows the hat number of everyone except themself, each person is taken to a separate room and asked to put on either a white or black shirt. Finally, all of the players will be taken into a large room and made to line up in hat number order (smallest to largest).
The goal of the game is for the players to devise a strategy by which, when they are ordered by hat number, their T-shirt colors will alternate. Given these rules, they are allowed to discuss a strategy (before seeing any hats). What strategy should they use to guarantee a win?
And here's another, simpler one:
You are playing a game with a genie. The genie, being magical, is capable of producing any real number, even ones which are not computable. The game is taken in turns, where each turn the genie will write a number on each of two cards (he can write very small!) and present these cards to you face down.
You can take pick one card and read its value. Then you must bet whether the card you selected has a higher or lower value than the other card.
Other than that the genie will never write the same number on both cards, you know nothing about his procedure for choosing numbers. What should your strategy be to ensure that you have a greater than 50% chance of winning every turn? Assume that you have a computer with a bit of genie magic to allow you to perform whatever mathematical operations you want on the numbers you're given (i.e. don't worry about practical limitations with calculations involving your numbers, random number generation, etc.)
Also if you use the prisoners and warden question (I assume you're referring to the one with the room and the light switch), you can add a bit of trickiness by not specifying whether the switch is initially turned on or off. This is still solvable, but requires a bit of a modification to the solution.
Answers provided on request. If I remember any more, I'll add them here.