D&D was originally a game about exploration and resource management with combat elements (sort of a Tolkienian Oregon Trail game). It quickly developed elements of heroic narrative, due to the nature of the setting. Based on my understanding of the rules, 1st, 2nd, 3rd, and now 5th Edition all attempt to maintain this tension between the "how many arrows the PC can recover post-battle" part of play versus the "hitting the Dragon in the heart with the PC's last arrow" part, but the 4th Edition rules seemed to have abandoned (or made irrelevant) the resource management part of the game. The rules have sections on equipment, the effect of weight,on movement, and such, but the allowances are so large that they have little effect, RAW, in how the characters interact with the game world. This accounts, I think, for the complaint that 4e "didn't feel like D&D".
In other words, I don't think it's a "grittiness" factor, in itself, that is the source of the complaint. One can,pump up the danger of a 4e game quite easily. It is, rather, the idea that the characters can effectively ignore mundane matters like "do we want fried rat or fungus sandwiches for dinner?" and "Drat it all! We didn't bring enough sacks, again. Get all the gold coins and as many of the silver ones as we can. Leave the copper coins. Do you have the map? Good, let's get out of here."
4e is still my favored edition.
I haven't read all of the other posts, but the reason why 4e doesn't feel like D&D to me is that it drastically changed. Having played since the '70s, it was relatively easy to transition our campaign to each new edition. Not so with 4e, it was redesigned from the ground up.
1) They changed the mechanics.
Open ended AC, attack rolls, ability scores, etc. all increasing at each level. This is a big part (for me) that makes it "feel" like a video game. When I check out a video game, and 4e, I have no reference point for what an AC of 45 is. I know it's more than 20, but I can't relate to it.
In all other editions of the game, armor itself sets the baseline. Even thought the d20 system reversed the way AC worked, it is still very easy to identify what a good AC is (anything that is equivalent to plate armor or better, for example). This problem exists across the math of 4e, as there is no "in world" reference to what the numbers mean.
2) They changed the world(s).
They decided that D&D (the core game) didn't have lore of its own. It was borrowed, or dependent upon campaign setting. So they made up a new base lore. Most elves are no longer elves, now they are eladrin, for example. Genasi are no longer mostly human with perhaps a few discernible features, they have glowing energy lines, and hair of crystal or some other element, along with a bunch of abilities. And to make sure that the new lore wasn't viewed as optional, they forced the new lore into the established campaign settings. The new cosmology, the new races and classes and all of the abilities, etc.
3) They changed the balance.
Or, balance became one of the central themes. All classes and races should be balanced across the same level. Encounters should be carefully balanced against those characters. And the biggest change - balance is relative. This relates back to #1 - 13th level characters are met with about 13th level challenges. The theory is that it doesn't matter if those challenges are impossible for 1st level characters, since they aren't 1st level.
4) They changed the focus.
Sure, you could (and many people did) maintain the exploration and role-playing center of the game in 4e. But it was primarily designed around providing more options, and carefully balancing, combat. While this probably wasn't the intent, they wrote a lot of the creativity out of the game. With so many rules to provide "interesting" options in combat, it becomes a game of managing your abilities and how best to use them, rather than a focus on the character and the story of that character. If a group of mid-level adventurers can get together to play for 2-4 hours once/week, and the adventure jumps from set-piece to set-piece, rather than providing a setting to explore, and the combats take anywhere from 30 to 90 minutes, there isn't much room for story, character development, etc. The focus is combat. Or making sure your character has interesting things to do in combat.
The focus is very much a munchkinizer's dream because you can spend so much time designing a character mechanically, rather than from a personality. But it also has the problem that if you aren't that into building the perfect (combat-oriented) character, you can feel left behind. It's much the same way as when my daughter and I recently played MtG for a short while. She liked the idea, it was fun when the two of us just picked up a set of two decks and played. We even enjoyed picking up a few new cards and building different decks. Until she tried to play a couple of people hanging out at the gaming store. She couldn't ever come close to winning. Because her decks were built on story, using cards that she liked for their appearance and lore. But that wasn't fun when all she did was lose. The real game in MtG is deck building, or you just copy somebody else's which isn't much fun either.
The real game in 4e was character design. For many home campaigns, not as much, but as soon as you had one or two players that really got into digging into the options and combinations, it can break many games.
The reality is, the 4e is a very well designed game, on its own.
But as an iterative edition of an established ruleset, not so much. The biggest flaw for me was that it was treated in a manner similar to MtG. A new edition can bring new lore, new creatures, new abilities, and...it's the same game. Except it's not. When playing MtG you don't need to invest in the story arc or the campaign setting to play the game. It really is just fluff. But in D&D, the fluff is a large part of what makes the game what it is. Not specific fluff. If you want to create a new world where elves as such don't exist, and a new race called eladrin do, that's fine. But to say that for the past 30,000 years in the Forgotten Realms, everybody was wrong, and now they all call elves eladrin, and they have different abilities and such? It doesn't work so well.
Whether you track arrows or not, ignore mundane activities, or whatever, that's all been part of the game. Really, all of the parts of 4e have been and continue to be part of the world of D&D in some way or another. But the 4e rules heavily encourage a particular focus and play style. While that trend was already happening, one of the biggest things that I think makes D&D D&D is that there is no one way to play it. If 4e fit your play style, or if you were a new player coming from video games or MtG, then you have a good chance of really liking the game. But if you were running an existing campaign and wanted to move into 4e, it was much harder, if not nearly impossible.
I will also say that looking back at it more, there are a lot of things that I thought 4e did, and it really didn't. But that was the perception we had, largely because of the presentation. And the presentation was a
huge part of why we didn't like the new edition ("Play this race if you...want to look like a dragon"). But I pick up a book like the
Forgotten Realms Player's Guide to flip through it again and maybe look for ideas, and there's almost nothing I can use in my 30ish-year Forgotten Realms campaign, and there are still a great many things that I'll start reading and I actively hate. That's on me, but it basically tells me that it's not the right edition for me. (I should also point out that there are quite a few things in the BECMI line that are the same way for me).
I still think that if 4e was not called Dungeons & Dragons, it would have received almost entirely positive reviews. On the other hand, it would not have sold nearly as many copies if that were the case, because D&D has a salability that a "new game" doesn't have. There's a long thread about Lore vs Rules that has shifted mostly to a discussion on canon. I think that 4e is a good example of when a company goes too far beyond what many of their customer base considers acceptable changes to a system and settings before a significant portion of them decide it's no longer the same entity. Or at least too quickly. I think 3.5e shows that significant change is possible without such a backlash if it's done in a more gradual way (because now I'm seeing more clearly how different 3.5e is from AD&D).