Actually, in my eyes WoW has pushed the idea of storytelling in MMO's forward. The game is much more dependant on quests than previous MMO's. It isn't until you get into the upper levels that "grinding" really becomes necessary. In fact, my highest level character is only 54 because I refuse to do anything that isn't directly related to a quest. Sure, some of the quests are generic kill 10 skeletons, but I still see those in single player games too.
The problem isn't with storytelling, it's with character impact upon the world. WoW tells quite a few stories, and it even has a few in game cinematics, but you're not making an actual impact on the gameworld. There is no easy solution to this problem.