Do the mechanics and gameplay in your game feel like they're an extension of your characters or story? Do they echo the theme or themes of your story? That's the ideal.
Just to make your life more complex, however, I'll toss something into the mix that seems to contradict the ideas in this chapter.
I've worked on many games that started not with a character, nor a story, nor with an overall vision of a game, but began with a group of gameplay ideas and mechanics that someone wanted to see in a game. Those having been decided upon, a story and game were built around them.
Even when working under such an approach, I still strive to take those gameplay ideas and mechanics and weave them into a story for which they have particular relevancy.
So whether I'm beginning with story or beginning with game mechanics, my approach is the same.
Still left undecided is this question: Is it possible that I've actually been granted the ability to see the future, and, knowing that a wiener dog invasion is at hand, have used this chapter to warn you so you can prepare for the end?