Here's my view. If you just play with it, it's a toy. A toy with a goal is a puzzle. If you have to make non-trivial choices to solve the puzzle (ie, there's some form of interesting challenge), it's a game. If you play against other players in an organised competition, it's a sport. Almost any multiplayer game can be turned into a sport, and a few (eg, Q3A) are specifically designed for this purpose.
The presence of a story is largely irrelevant to the question of whether it's a game or sport, though clearly if a game contains not much else but story, it probably can't be called a game (some interactive fiction works are in this category).