I can't wait to give it to my young son and see what he can do with it.
Regarding Turing-completeness: Perhaps you can write maintainable code in Intercal or Whitespace, but most people can't or at least don't want to write maintainable code without functions and static scoping.
If he's learning to read, there's http://scratch.mit.edu/. Scratch doesn't really have a native version for Linux though - you can wine it, or you can try the (somewhat unofficial) build at the following link. I've tried both, and they work alright.
Here's the best guide I've seen this far for installing Scratch on Ubuntu: http://scratch.mit.edu/forums/viewtopic.php?pid=52179#p52179
