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.
Scratch runs on Squeak Smalltalk apart from some features that require a Scratch-specific native extension to Squeak. Scratch is not free software, so no wonder distros don't package it. The Scratch guys have a package for the OLPC though.
I decided to start with a little python...just a little bit to add or subtract a number repeatedly. He was able to follow it, but not, of course, do it the first time. Maybe if his interest remains, he'll start playing with it be himself!
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