The Sleeping Beauty problem and the other "paradoxes" of probability are problems that have been selected (in the evolutionary sense) because they contain psychological features that cause people's reasoning to go wrong. People come up with puzzles and problems all the time, but the ones that gain prominence and endure are the ones that are discussed over and over again without resolution: Sleeping Beauty, Newcomb's Box, the two-envelope problem.

So I think there's something valuable to be learned from the fact that these problems are hard. Here are my own guesses about what makes the Sleeping Beauty problem so hard.

First, there's ambiguity in the problem statement. It usually asks about your "credence". What's that? Well, if you're a Bayesian reasoner, then "credence" probably means something like "subjective probability (of a hypothesis H given data D), defined by p(H|D) = p(D|H) p(H) / p(D)". But some other reasoners take "credence" to mean something like "expected proportion of observations consistent with data D in which the hypothesis H was confirmed".

In most problems these definitions give the same answer, so there's normally no need to worry about the exact definition. But the Sleeping Beauty problem pushes a wedge between them: the Bayesians should answer ½ and the others ⅓. This can lead to endless argument between the factions if the underlying difference in definitions goes unnoticed.

Second, there's a psychological feature that makes some Bayesian reasoners doubt their own calculation. (You can try saying "shut up and calculate" to these baffled reasoners but while that might get them the right answer, it won't help them resolve their bafflement.) The problem somehow persuades some people to imagine themselves as an instance of Sleeping Beauty selected uniformly from the three instances {(heads,Monday), (tails,Monday), (tails,Tuesday)}. This appears to be a natural assumption that some reasoners are prepared to make, even though there's no justification for it in the problem description.

Maybe it's the principle of indifference gone wrong: the three instances are indistinguishable (to you) but that doesn't mean the one you are experiencing was drawn from a uniform distribution.