Length. A game is always longer to new players, of course. But if it takes too long for new players, will they play again? Length is of course quite dependent on how much players enjoy what is happening in the game. The boardgame Civilization can take 8 to 12 hours, but those who love the game don't find that time weighs upon them.
Down time. Downtime is the time people must wait while someone else is taking a turn. This can be a problem even in a turn-based electronic game. Do people get bored waiting for their turn?
Is the game balanced. Even if the game is symmetric (all players start with identical situations), is there an advantage to playing first (or last). Chess is symmetric except for who moves first, but move-first is a big advantage.
Dominant Strategy. Look for any dominant strategy ("saddle point"). This is a strategy that is so good that a player who wants to win must pursue it; or a strategy so good that some will pursue it, yet that strategy renders the game less than entertaining. For example, in a Euro-style 4X game I've designed, one player found that by getting together a sufficiently large force, along with certain technology research, he could completely dominate other players who weren't pursuing the identical strategy. I want the game to offer a variety of ways to success, so I had to change the rules fairly extensively. This is why it is very important to have testers who are dynamite game players, so that they'll find these strategies during testing, rather than have someone find it after the game is published. I'm luck that I have one such player, and that I can be such a player myself when I put my mind to it.
Analysis paralysis. Are there too many things to watch for or keep track of, or too many choices, so players either freeze up or give up on figuring out what is the best thing to do? There are always "deliberate" (slow) players, the question is, is everyone slow or frustrated?
Rules difficult to grasp. What do the players find hard to grasp. (In my prototype Age of Exploration, players had trouble grasping the difference between movement of units and placement of units. I used the same distinction in an abstract stones-and-hexes prototype, and no one has a problem. Even if, after playing, players "get it", it might be necessary to change something. (In AoE I changed the rules extensively to recast/eliminate the distinction.)
What do players tend to forget? This isn't quite the same thing as what's difficult to grasp. Some rules just don't stick in people's minds. Is there anything you can do about it? Is there some play aid to help people remember?
What do players not bother to use? Some rules exist but no one uses them. If the threat of using them is not making a difference in the game, then perhaps you should eliminate the option. For example, in my hex-and-stones game Law and Chaos I originally allowed people to move a piece rather than place one. This happened rarely, as it was usually better to place another piece and increase the number on the board. So I eliminated the possibility, except as an "optional rule".
This was done in some haste, and I imagine I'll think of more.
Here are some items added from comments on boardgamegeek.
To see the discussion on boardgamegeek go to http://www.boardgamegeek.com/article/1810302#1810302
Adequate control. Do the players feel that they can exert a measure of control over what happens in the game? Remember, any (strategic) game is a series of challenges and actions in response to those challenges. (Harmony)
Horns of a Dilemma. On the other hand, are there enough plausible decisions in a play to make the players think, but not so many that "analysis paralysis" sets in. Even in a simple game, if a player can do only two of five possible actions in a turn, is there tension here or are the plays obvious? As one commenter put it, do the players sometimes feel "so much to do, so few actions"?
Player interaction. Do the players have to take the plays of other players into account? Yes, some games are virtually multi-player solitaire, and some players are happy with this. But most players want to be able to affect other players with their moves.
Taking it to the Max. Can extreme behavior within the rules break the game? Sure, if someone pursues a bad strategy, they'll lose. The question is, is there some extreme strategy that results in an unfair game?
Components and Play Aids. Do the physical parts of the game help play flow smoothly, or does something need to be changed? Is there too much record-keeping? How can it all be simplified?
Stages of play. You probably learn this in alpha/solo testing, if you do solo testing (which I strongly recommend). Are there identifiable stages in the game, especially ones where the typical run of play changes? E.g., in chess there is the early, middle, and end games. Pieces are deployed in the opening, mix it up in the midgame, and so forth. An exploration game has the expansion period followed by consolidation and then (usually) conflict. Etc.
Player interest/"fun". What part(s) of the game seem to be most interesting to the players? I'm not in favor of trying to figure out "fun", because fun comes from the people who are playing more than from the game design itself. And there are many games that I wouldn't call "fun" (including Britannia) that are nonetheless interesting and even fascinating.
Finally, remember Antoine de Saint-Exup'ery's maxim: “A designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away.”
"The worst form of inequality is to try to make unequal things equal." -- Aristotle
"Always do right--this will gratify some and astonish the rest."Mark Twain
"A designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away." Antoine de Saint-Exup'ery
"Not everything that can be counted counts, and not everything that counts can be counted." Albert Einstein
"Make everything as simple as possible, but not simpler." Albert Einstein