I think asking fighting games to have better stories isn't fair as they don't have much to build on. The story is usually that there is a tournament and everyone's invited. To tell a great story from there would mean you would have to really go into each characters back story which would take ages as most fighters these days have at least 20 characters if not more.

Saying that, there is fun to be had with the story, as long as the developers don't take it so seriously. Tekken 3 is a good example. The ridiculous ending movies were so entertaining that they really motivated me to beat every character on arcade mode.