I stumbled across an article in Lifehacker called Ruby For Kids Teaches Your Kid (And Yourself) The Ruby Programming Language. The article talked about how to get your kids involved in programming games through an easy to use language called Ruby on Rails.
I setup the Ruby programming environment for Nate and gave him the link to the tutorial. After dinking around with getting the programming environment setup right, he started watching the video tutorials and ended up making a very cool video game, a pac-man type game. He's moving on to the next level with another book I picked up for him called Ruby on Rails 3 Tutorial. Nate's 14 and I think he connects with the problem solving aspect of programming that's similar to the problem solving aspect of video games.