Previous posters have pretty well nailed down the difference between a "toy" and a "puzzle or game"; puzzles and games have a goal, whereas toys are just meant to be played with until you're sick of it.
I would define the difference between a "game" and a "puzzle" as the element of competition. In a game, you're competing against something: another player, an AI, time pressure, &c. Essentially, you might lose a game through the action of another agent, whereas with a puzzle the only way you fail to win is by giving up.
This definition automatically implies that competitive puzzle-solving becomes a game, which makes sense to me. Also, puzzle-solving against a countdown timer becomes a game, which is again fine with me.
Stated another way, my distinctions among these three terms are their ending conditions.
- toy: give up
- puzzle: win OR give up
- game: win OR lose OR give up before completion
Note that altering your perspective can move a particular artifact among these categories. Generally, expanding your time scale will tend to move an artifact up the chart. For example, each life in Portal is clearly a game; either you beat the level, or GlaDOS kills you. However, Portal as a whole is more of a puzzle, since in the end you WILL either figure out the way to beat the level, or you'll give up; GlaDOS never permanently prevents you from trying again. Completing a shelter before the monsters get you in Minecraft is a game; eventually completing your shelter, possibly with many respawns, so that you'll be safe from monsters in the future is a puzzle; Minecraft as a whole is clearly a toy (it has no built-in permanent end condition).
This classification isn't perfect, of course. Dwarf Fortress is an interesting example. As a game, your objective on a single embark is presumably to create a fortress that can... something. Hmm. As a toy, the possibilities are limitless; I've seen a 4-function calculator implemented in DF (yes, this is
insane awesome). The problem with my classification is that any given DF fortress clearly has a lose condition, or you can stop playing (give up), but it has no obvious win condition. You can set your own win condition, which clearly makes it a game, but without doing so it doesn't really fall into any of these possibilities. Possibly I need a 4th category for "toys that menace with spikes of evil" to fit a single DF fortress into.
EDIT: I think Joe Wreschnig nailed it in the comments. The essential difference between a game and a puzzle is that a game can be lost, whether through competition, a timer, or whatever. I was kind of working toward this but couldn't quite articulate it. Thanks Joe!