Shinigami357 has it right....the whole point of the Pokémon games is to battle, trade and interact with OTHER PEOPLE, with single player giving you a basic story so you can get the hang of battling. When people judge Pokémon for its generic "catch Pokémon and beat the gym leaders" story, they are not judging Pokémon, except they are judging the entire experience based on a simplistic story only tagged on to help people get the hang of the game, and once you complete the story, you move on to the multiplayer aspect of the game, where the real experience is.
And when you look at the multiplayer aspect of the game, you will see that each generation is different in their own way. Through each game that is released, they add new pokemon, abilities, strategies and moves. These changes are pretty huge when you focus on the Pokémon's biggest strength, because now all your old strategies will probably not work anymore with the inclusion of new Pokémon, moves strategies etc, so you have to discover new strategies based around these new moves etc to give you the edge over your opponent. To make this bearable they tack on the same basic storyline, and by the time you complete it, you should already be familiar with all the new stuff they added in.
And addressing the point of the formula changing, no, the basic formula is fine as it is, what's not fine is either keeping it the same (by the same I mean absolutely nothing changing since Red and Blue/Green or completely revamping it, which then it's not Pokémon anymore), what you do is keep the basic formula but improve on it slightly, so while the battling aspect seems familiar, it enhances it, creating a new experience all together What I am trying to say here is that if you are going to judge Pokémon, then focus on what made it so popular in the first place (the multiplayer), as without the social aspect of the game, Pokémon would be nothing, and if you are not playing Pokémon for the multiplayer experience, but for the story, then you really shouldn't be playing the fucking game(s) at all.
The storyline is also fine as it is. Basic explore the new land and defeat the gym leaders / elite 4, once that done train your Pokémon with the post game content they provide, good fun on the side when you're not battling (or trading with) other people, and while it may seem like a grind, well it's only one when you try and blitz through the game.