Not sure about any puzzle games on the GCN.  I really don't recall anything that stands out.  For Wii however, you do have Mercury Meltdown Revolution, Puzzle Quest: Challenge of the Warlords (if he has yet to play it, tis an awesome puzzle/RPG hybrid), Kororinpa: Marble Mania and Geometry Wars: Galaxies which is a sequel to the original game born on XBLA.

All of these games are budget priced, the most expensive being Puzzle Quest (which comes out towards the end of November) at around $30.  Of them all, I would strongly suggest Puzzle Quest (I plan on getting it as I can't find the DS one anywhere) followed by Mercury Meltdown Revolution.  Geometry Wars: Galaxies should be decent as well though I'm not sure if I'd totally classify it as a puzzler as it's a lot closer to being a progressively advanced Asteroids and even that description isn't enough to really say all there is to say about it.

Kororinpa is decent, but fairly short and not very challenging until towards the very end of the game.  For a puzzler involving marbles and rotating landscapes as you navigate courses and mazes, it's pretty decent but shallow compared to MMR and Puzzle Quest where modes, features and general content is concerned.