I think what they are really objecting to is not a lack of realism in the sense that like your character jumps too high or you can take waay too many bullets without dying.
What they mean is that the "reality" in the game isn't consistent. For instance, a military shooter creates a really strong impression that it is based in a realistic combat setting. there is bullet recoil, headshots instakill, etc... But then the game has elements that are totally "unrealistic" given the impression of the games reality we have been given. Like a grenade goes off point blank at a target but he doesnt die. Then it doesn't add up, the immersion is broken and it feels fake or unrealistic...
Nobody cares that mario bros isnt realistic, because its established right from the start that the rules of reality do not apply and how things work.
Edited by mothrpe - 4/18/11 at 11:33am