On the puzzle side of things, I often worry that the puzzles I design will be too easy for everyone. It's hard to be objective when you know how it works and have played the puzzles hundreds of times
Under these circumstances, I would think that being objective about a puzzle's difficulty would be next to impossible.
I know there are gamers who finish an adventure game and feel dissatisfied because it was too "easy." I have never felt this way. I don't think I've ever played a game where I considered the challenges to be too easy. Even "The Legend of Lotus Spring" had me stuck for awhile in a couple of places.
I have sometimes wondered if the complaints of "too easy" meant that the game went by too fast if the gamer used a walkthrough. Some games have challenges that, once you use the walkthrough, are solveable with a few mouse clicks. Enough of these in a game and the game seems too "easy" (even though the gamer would have been far more challenged if s/he had attempted the challenges without cheating).
On the other hand, puzzles that are randomly generated and can't be solved with a walkthrough then make the game too "hard" because cheating isn't allowed.
I know, I am being extremely cynical, but I have seen posts where a game was described as easy and then the gamer mentioned using a walkthrough.
I would imagine that part of designing a game is to create an environment that steers the poor, muddle-headed gamer in the right direction mentally so as to be in the correct frame of mind for understanding how to approach puzzles and challenges. I'm not sure how this is done, but when it's done well the game is tremendously fun. The game makes you feel as though you are a lot smarter than you know you really are.