I agree that fresh stories are harder to come by. Its a byproduct of the corporate culture pervading mainstream gaming. They have to go with whats worked and if you're lucky, they'll put a twist on it.
Maybe try more indie games? Go to the Underground section of this website and try some of the games there. You'll definitely find some original stories there.
