First, I think it's important that a game never be frustrating. This is one of the principles of
flow, and more importantly, when a game is frustrating, it really disrupts the player's immersion in the game.
To that effect, one of the most frustrating game elements that I see time and again is the age old "die, fight, repeat" formula.
This is, quite frankly, annoying and has been done before.
Don't get me wrong, some risk is required to have fun (coincidentally, it is also another principle of flow), but a game which forces the user to repeat themselves is a game that's run out of new ideas.
I've seen some variation on this formula in the past with decent success, like bullet time effect, which allows the user to "cheat" and slow down the game when the going gets tough. However, it's still a very constrained way of tackling the problem.
Thinking a little outside of the box, I'd like to see adaptive story lines, where based on a player's proficency and style, the story line changes in sensical ways. Also, tiered reward systems based on proficency, not on difficulty, and new ways to handle character death through story telling elements like ghosts, time warping (maybe the ability to go back or forwards in time?), etc.