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.