Another one that seems of similar difficulty to Cheryl's birthday is http://en.wikipedia.org/wiki/Ages_of_Three_Children_puzzle (the article contains spoilers):
A census taker approaches a woman leaning on her gate and asks about her children. She says, "I have three children and the product of their ages is seventy–two. The sum of their ages is the number on this gate." The census taker does some calculation and claims not to have enough information. The woman enters her house, but before slamming the door tells the census taker, "I have to see to my eldest child who is in bed with measles." The census taker departs, satisfied.
What are the ages of the children?
I actually remember finding blue eyes easier than three children, but I don't remember my relative ages when I first heard them, and I discussed both with my family at the time. But blue eyes had an "obvious" approach which worked after routine application, and three children/Cheryl require you to extract a different insight from every step of the puzzle.
If it's worth saying, but not worth its own post (even in Discussion), then it goes here.
Notes for future OT posters:
1. Please add the 'open_thread' tag.
2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)
3. Open Threads should be posted in Discussion, and not Main.
4. Open Threads should start on Monday, and end on Sunday.