We are told:
>"It does not always give the best advice possible in a situation. It will not necessarily make its wearer King, or help her solve the miseries of the world. But its advice is always better than what the wearer would have come up with on her own."
I think one very simple explanation would be that this comes down to a matter of exploration vs exploitation. Since it is only giving "better" advice, and not even 'locally optimal', there is reason to favor exploring vs merely following the advice unquestioningly.
A more complex, but ultimately comprehensive answer, is that free will consists, at least in one aspect, in the ability not only to choose one's goals or means, but also what _aspect_ of those various options to consider "good" or "better".
And if one were to say that all such considerations ultimately resolve back to a fundamental desire to be "happy", to me, this seems to be hand-waving, rather than addressing the argument, because different people have different definitions of the "happy" end-state. If these differences were attributed fully to biology & environment, the story loses its impact, because there was never free will in the first place. If, while reading the story, we adopt a view that genuine free will exists, and hold some kind of agnosticism about the possible means by which that can be so, then it seems reasonable to attribute at least some of the differences in what the "happy" end-state looks like to the choices made by the people, themselves.
Given that kind of freedom, unless one has truly perfect knowledge (beyond the partial knowledge contained in the advice of the earring), the pursuit of one's goals seems to unavoidably entail some regrets. And with perfect knowledge, well... The kind of 'freedom' attributed, for example, to God by philosophers like Thomas Aquinas, is explicitly only analogous to our own, and is understood to be an unchanging condition, rather than a sequential act.
(As a final note: One might wonder what this 'freedom to choose aspects' approaches as an 'asymptotic state' -- that is, for an immortal person. And this leads to metaphysical concerns -- of course, with some things 'smuggled in' by the presumption of genuine freedom, already. Provided one agrees that human nature undeniably provides some structure to ultimate desires/"happiness", the idea of virtue ethics follows naturally, and from there many philosophers have arrived at similar notions of some kind of apotheosis as a stable end-state, as well as the contrary state of some kind of scattering or decay of the mind...)