Oh man. I did know a new puzzle was coming for a while though. A few weeks ago I streetpassed some from Japan (even though I live on the other side of the globe) who had a puzzle marked as ???. When I tried to take a piece, it told me "This puzzle must first be downloaded through Spotpass" or something like that.
I suspect it's a large one, i.e. 8 pink 40 total pieces. It's almost impossible to complete the new puzzles though. I have all purple pieces except for those of the Kirby Anniversary and NSMB2 puzzles.