They can be annoying for the person in charge of the game, because they can be hard to design. Granted there are lots of puzzles out there you can borrow, but if you want a unique one you are left to design your own. This means you need to figure out how the puzzle works, how it doesn't work, what clues there are to figuring it out, and so forth. Then they can get really frustrating, as the most likely result of presenting a group of people with a puzzle is either 1) it clicks with someone right away who just walks up and solves it, thus what could have been hours of work for you is only seconds worth of game time in the actual game. 2) They don't get it at all, and it completely derails the game.
#2 is where things get really bad for the player as well, nothing is worse or more frustrating than a puzzle that you can't figure out, can't get help with, and need to solve to get through. Well, that's not true, there is one thing that is worse, and considering I've spoken about other pitfalls with puzzles before in here I'm going to go right to it. The only thing that is worse than a puzzle that doesn't just click for you, is one that doesn't just click for you when you're in combat.
To illustrate my point, I'm going to use an anecdote. On numerous college campuses around the country there is a game called Humans vs Zombies. Essentially, a zombie infection on campus and the human players have to survive through the game. They survive by being able to stun zombies with either NERF guns, rolled up socks, or marshmallows. Zombies 'bite' humans by tagging them with out being stunned. In UMass's game this year, the Admins added a third force to the game to try and mix things up a bit, Human soldiers who were neither with the humans or the zombies and who were armored in a way that made them only vulnerable to specific things. The admins then warned players of this by putting in the rules that some NPCs could only be killed in certain ways, and it was up to the players to figure it out. Wonderful, there is a puzzle in the game that comes up during combat, that should add tension and make things a lot more fun for everyone involved right? Wrong. Only one mission in and people were complaining about this mechanic, on the second mission when the solution to the puzzle changed some people were agitated to the point they wanted to quit. As the game went on, the puzzle got more and more complex and people got more and more annoyed. Why?
Well, two things. One, the hints were too vague, meaning that the solution to stunning these Soldiers was harder to find. Was it one specific ammo type? A combination of 2 of them? Maybe a combination of all 3 ammo types? Now, this doesn't seem all that complex now does it? Just hit them with one of everything, and work from there if it doesn't work. Except for two things. 1) When put in a tense situation, many people seem to lose the ability for logical thinking involved in puzzle solving. This isn't surprising per se, tension brings about your fight or flight response, your ability to rationalize is reduced as your body goes into survival mode. Need to punch someone out? This is the mode to be in! Need to run faster than you thought you could? This is the mode to be in! Need to figure out a puzzle whose solution isn't obvious? NOT the state of mind to be in. #2) The feed back on the puzzle also wasn't good, meaning that there was never really a sign of progress, or if you were even close to the solution. In short, the solution could be anything, you never knew how close or far you were, and the tension only increased as your team began to lose members and you were trying to participate in NERF gun combat, stay from being tagged, AND solve a puzzle all at once.
The end result? Most people I've spoken to thought the idea was neat but horribly executed. Many people claimed that the game was not Humans vs. Zombies, but instead Humans vs. Admins. Of those not calling it that, numerous were still saying that the Admins were more of a threat than the Zombies, and that the Admins weren't out running the game they were trying to win it themselves. In RPG terms, this is the same as the GM trying to win by "beating" their players. Not really a good thing to do, in my opinion at least.
Another anecdote for it, this one involving RPGs. A few years ago I was the Head GM for an online RPG. In one of the big battles, I made a group of enemies that I called "the Deathless". The Deathless worked in groups of 3, 5, or 7 (or any odd number, preferably prime, really). If only one of them was still standing at the end of the round it let out a loud piercing howl that could stun players, and would revive all the slain members of its group to continue the fight. The trick to beating them was simply to not have only one left standing at the end of the round. Simple right? Turns out, not so much.
The five deathless engaged the 4 PCs (Deathless have horrible attack rolls to help balance their undying nature). The PCs made short work of them, killing 4 of them in 2 rounds without taking a hit, wondering if perhaps I had been joking when I said this would be a tough battle. The last one screamed, his 4 dead friends got back up, and people started wondering what was going on. 10 rounds later the Deathless had revived themselves for the 3rd time, two of the PCs were down (unconscious, not dead) and I had begun putting things in my description like "down to only one once more, the very last standing monster lets loose a loud piercing howl that revives his fallen comrades". I really didn't think I could be more clear. Some other PCs wanted in on the scene, being down to only 2 PCs still in fighting status and them heavily wounded I agreed. They also didn't figure out the problem. Roughly 20 rounds in I finally relented, gave someone an intelligence roll and flat out told them "It only happens when there is one left right? Maybe you should try making sure there isn't only one left at the end of the round". The PCs were "victorious" three rounds later.
So what is the solution? As I said, many people liked the idea, just not the execution for HvZ and people still say the like the Deathless I used. It also is a good idea in a sense, it adds a level of flavor while upping the tension by making combat not about dice rolls and how much damage you can put out, but by how you put out the damage. The solution is simple, you need to give clearer hints about the thing in question, and give feed back during the encounter to show how far along they've been getting.
In the HVZ game this could be as simple as warning people more clearly in the mission briefings "Soldiers are vulnerable to one type of ammo only" or "A specific combination of 3 types of ammunition (nerf, sock, marshmallow) is needed to stun a Soldier". It is essentially giving away the puzzle (if it were not a combat puzzle) but they still have to work for the solution. With the Deathless, the only thing I can think of is just being more clear about the solution than I was, giving the intelligence roll for advice earlier on. I'm biased on it, but I think I did everything I could, and it is just more of an example of rational brain not working in 'tense' situations.
If you are going to do puzzles during tense situations in your game though, you need to be aware that you need to make the puzzles a bit easier, and be more willing to work with your players on the solution. A tense situation with a puzzle that can't be solved gets people frustrated, pissed, and angry (yes, all 3). It can cause problems for the game, and the relationship. Not handled right it can shatter the trust between a GM and their players, which can make everything else in a game suspect.
So use them, but be careful when you do. Warn your players before going into the fight (or the session if you don't want to give it away) that the encounter (or an encounter) is going to be more puzzle based than standard combat, and to make sure they have their thinking caps on for it. The warning, hints, and working with them can keep it fun even if they're not quite getting it.