When I was in 6th grade, computer class used Apple II's and we learned out of the Kids and the Apple II book, which took us through the basic language from the ground level and, looking back, I think it did a decent job of teaching us programming concepts in a fun way. I think this background gave me a good foundation of programming that helped me even through college C++ classes.
But I'm not writing to specifically recommend that book, but to share my observation about that time period of learning. Sure, we had our share of boring calculator programs, and I wrote a fair amount of spaghetti code, but the most fun we had was when the teacher assigned us to write an adventure game, in the vein of choose your own adventure. Since textual and graphical adventure games were what we liked to play at the time, it was a real thrill to be able to try to create even a pale imitation of them.
But then things got too complicated. Games got to good so it wasn't really possible to imitate them on a low level. If you learned C or C++ in class, it was really difficult to create games or GUI apps without learning all these other tools and platforms. Programs had to be compiled and took all the immediacy out of trial and error programming.
Years later, when the web came along and everybody was hand-coding or frontpage-ing static HTML pages for their "homepages," I never got into that. I knew that the professionally done sites like yahoo or amazon weren't using static HTML but had server generated pages. When PHP finally came around with the ability to programmatically generate web pages, I felt a thrill just like back in the BASIC adventure game days. I could create media the same way those "in power" created it.
Today's kids are voracious consumers of media, but they like to create it too. Whenever tools come along that let them create media "just like the pros," they jump on it. For example, when CD burners came around, everybody made mix-CD's just like the compilation CDs sold commercially. When sound and video editing came out, kids jumped on that, first using DVD burners and then YouTube.
Following this observation, kids nowdays live on the web. To them, Facebook is professional media. If they could create dynamic sites like Facebook, they would feel the thrill of creative programming and be able to connect with the reason for why people program computers.
For this reason, I think one of the web-oriented languages like PHP or Ruby is a great way to introduce programming to students. They can build pages like what they use and see the results in their web browser immediately without compiling and feel the thrill of creating again.