Hmm, characters sharing a lot of moves and differentiated by special moves? Sounds like the Smash Bros. games to me, which is undoubtedly a very popular franchise. (They’re starting to buck that trend with characters like Mega Man and the Villager though.)
I think Smash Bros. also limits itself to about 40 to 60 moves per character. I don’t think having a huge amount of moves is a bad thing–you just have to get more milage out of each move, design-wise.