I'm surprised nobody has mentioned Doug Hellman's great resources. His book "The Python Standard Library by Example" is basically a print version of his PyMOTW project (http://www.doughellmann.com/PyMOTW/). While not an end to end "learn Python" the examples, at least in my case, have led me to ask quite a few questions that open other doors into Python that I haven't been exposed to.

I like what Zed has put out, but the books Lutz has out are great as well. Hetland's book is OK and Paul Barry's "Head First Python" is a great read if you're a true beginner to get your feet wet with a fun book. It's an easy read, but I would think that the transition to "Learning Python" would feel like a slight step backwards - however "Programming Python" by Lutz may be a better logical step (instead of going back through a lot of the basics).