There are plenty of popular NP-hard puzzles, for example, generalized Sudoku ($n^2 \times n^2$-board), Flow (I cannot give a source for this), Minesweeper, etc.
Recently, I read a bit about aperiodic tilings of the plane, and it is undecidable whether a set of tiles can tile the plane or not, since there might be aperiodic tilings. I do not really consider this problem a popular game you would find in a newspaper.
So, my question is this: what puzzles/games are there that are undecidable in general?
The Post correspondence Problem, (PCP), is undecidable and this has a very "puzzle"-feel to it, so I would say this game could qualify.
Perhaps some generalization of the board game Roborally on an infinite board, would lead to some type of undecidability, that is, there is no algorithm that given a RoboRally configuration produces the resulting configuration after all rules have been applied?
As a funny note, the sand-box game Minecraft allows the user to make circuits, making the game (in theory) Turing complete.