I love the Head first series books. Even though I already had experience with other languages when I started, Head First Java explained things clearly and enjoyably! http://amzn.to/ybDBJv
I can't recommend Head First Java enough - initially I thought it was too whimsical and lacked depth, but it goes over key points simply and repeatedly until you understand them. If you have OOP experience then a lot of the first half of the book will be pretty familiar, but it's useful enough for the syntax/quirks etc
The Head First Series is "Learn the Hard Way" backed by modern educational theory - hands on, engaging multiple learning pathways, and offering problems at various levels of difficulty even on relatively advanced topics.
They are structured based on ideas about how people learn rather than ideas about how they should learn.
That's not say that "Learn the Hard Way" is not useful or that I don't admire what Zed Shaw is doing. I think it is really good work.