Undecidable puzzles 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. 
 A: This answer is not entirely serious, but it does not fit as a comment.
Numberwang is undecidable.
Numberwang, of course, is a fictional popular game show featured as a running gag in the real sketch comedy show The Mitchell and Webb Look. Here is a sample episode of Numberwang. The rules of the game are never explained, but they seem to follow this format: two players alternate calling out arbitrary numbers, and a computer program decides after each move if the string of numbers so far called constitutes Numberwang or not. The player who called out the last number before Numberwang was announced is the winner. The computer program which decides whether a string of numbers is Numberwang was covered in a fictional documentary special. Furthermore, it appears that the program is not a secret, since a home edition of the game is available, complete a with a multi-volume set of books that allow you to compute for yourself whether a string is Numberwang. So Numberwang is a perfect information game.
Surprisingly, a game very much like Numberwang - except limited to m moves and where only natural numbers may be called - is address in section 14.1 of this review paper. If the Numberwang-deciding function is allowed to be any computable function, then the problem of determining, given the Numberwang-deciding program as input, which player has a winning strategy is undecidable. Other interesting results are also given.
A: Typing "undecidable" and "puzzle" into MathSciNet turned up a couple of candidates. 
Baumeister, Dorothea and Rothe, Jörg, The three-color and two-color Tantrix rotation puzzle problems are NP-complete via parsimonious reductions, Inform. and Comput. 207 (2009), no. 11, 1119–1139, MR2566946 (2011c:68052). According to the summary, the infinite variants of the 3-color and 2-color Tantrix rotation puzzle problems are undecidable. This follows work by M. Holzer and W. Holzer [Discrete Appl. Math. 144 (2004), no. 3, 345–358; MR2098189 (2005j:94043)] showing the same for the 4-color Tantrix puzzle. 
Demaine, Erik D. and Hearn, Robert A., Constraint logic: a uniform framework for modeling computation as games, Twenty-Third Annual IEEE Conference on Computational Complexity, 149–162, IEEE Computer Soc., Los Alamitos, CA, 2008, MR2513497 (2010d:68039). This paper introduces a simple game family and proves "a game with three players and a bounded amount of state can simulate any (infinite) Turing computation, making the game undecidable." There are applications to many existing combinatorial games and puzzles. 
A: A recent (after the question was posted) arxiv preprint
proves that Magic the Gathering is Turing-complete.
The abstract states:

This shows that even recognising who will win a game in which neither
  player has a non-trivial decision to make for the rest of the game is
  undecidable.

