My daughter is following this book (Python for Kids) on her own now, and about a year ago we spent a while reading the Hello World book (http://www.manning.com/sande/) which is a very gentle intro to programming, Python and it was great. I liked Hello World a lot because it explained lots of terms in familiar language and the illustrations and characters were very funny.

She's 12 now so her expectations about games are more influenced by gaming consoles, so I think the next stop will be doing some simple stuff in the Blender Game Engine, which can be programmed in Python too, once she becomes more fluent on programming.

Both books use IDLE as the programming environment, which is fine, but expect to have minor issues along the way: you have to be aware of intentation rules (it's Python) and in one game the library name could not be found because the name started with a uppercase letter ("import Tkinter" in Ubuntu). In Ubuntu you may need to install some extra packages, etc.