If death is something that happens regularly beyond the control of the player, as opposed to doing stupid things (lucky criticals, etc.) then I think that's a legitimate issue. Dying is fun when you realize your mistake - when there are no mistakes to make, and death was beyond your control, however, it's no longer fun or interesting as a game mechanic, it's just punitive.
Mass Effect on Insanity, for all its challenge, always felt fair to me - I was losing because I made mistakes, rushed in, was careless, etc. In Call of Duty, on Veteran, I rarely die due to a lack of skill, but rather due to random chance. Death comes so quickly that there's almost nothing you can do to stop it (peek your head out at the wrong time? dead) and the game has a sick habit of throwing four grenades at you at once, with escape pretty much impossible. Winning in Call of Duty can feel more like luck than anything else, which isn't really appropriate to a shooter in my mind.