From a user perspective, you shouldn't even display an option for a user to vote if they have already voted on a story. Having a validation run before_save is a good way to make sure it doesn't happen, but the user shouldn't get to that point in the first place.
So, add a method to the User model (or alternatively, the Story model)
which will return true if the user has voted on story_id.
# check to see if the user has voted on the story
# something like
Then, create a helper method for your voting display
Code isn't tested, but it should give the gist of what I'm getting at.
[... code that display a voting link ...] unless user.has_voted?(story.id)