But that isn't really new. That's just a combination of two things that have been done before.  
 New Super Mario Bros Wii is basically retro Mario gameplay with 4 players co-op, Borderlands is just a shooter with rpg and looting elements. but they still count as a new experience and different kind of game.
The combination counts because combined formula makes it different from the formulas when they are separate.   Lemonade is different from lemons, sugar and water individually.
As for the other stuff they've added, yeah, it's a nice touch (except for how the characters were nerfed, like Sonic_Reaper was mentioning), 
But the nerf was necessary.  Even with what they have, Hard mode still becomes a joke once you have the good equips/hunter skill levels.        There's still enough there to have fun with each one.  
If anything, the one thing Castlevania HD should get is a Very Hard difficulty that continues to challenge the best setups. 
but it's mostly superficial. Besides multiplayer, they haven't really brought any new fundamental aspects to gameplay. It's essentially a multiplayer Metroidvania.
What's wrong with that?  it's some of the great reasons why it's still played to this day!  

It's better than totally reinventing the wheel and presenting a Pancake throwing Castlevania that has pancakes you can power up your whip with, which you can telepathically throw at enemies and talk to your whip like an intelligent snake friend that can move independantly and do the forbidden dance.
And the castle turns out to be a tree that absorbed the blood of Dracula, 
so now the castle is a super flying castle vampire tree that spews blood and the game only supports motion controls to launch pancakes from your whip and do moonsaults and your stat upgrades only take affect when the moon is full, and with full Heart meter you can turn into a chainsaw for a few seconds.  How's that for innovative gameplay?    Well one would ask "but are my favorite characters playable, is there an option to use the classic metroidvania gameplay and can I play it with 5 friends online?"  
I know it can be a fun game (in fact, I'm still playing it)  but I think it's deserving of the criticism it's received. 
Well ya it isn't for everyone and won't match everyone's tastes and preferences, but it really is one of the best things they've done in gaming history, and there really isn't anything exactly like it on consoles, even from a co-op standpoint, games like L4D, Borderlands, RE Outbreak and Guardian Heroes are completely different vegetables compared to this. 
Castlevania Harmony of Despair has become the new favorite for many fans, friends and gamers out there.  It's really deserving of praise too!  
