The books by Chris and Trish Meyer are good. They are the "Creating Motion Graphics with After Effects" books; there are 2 volumes: Essentials, and Advanced. They are presently current only up to AE 5.5, however they are still very relevant. Expect the Meyers to release new versions of their books some time after AE 6.5 is released. According to their Website, they only update their books for the ".5" releases of AE and plan to do so for 6.5.
For more advanced topics the Meyer's also have "After Effects in Production." I don't have this book yet, but I assume that it is very good and plan on getting it soon.
Agreed on the Meyer books. I have After Effects in Production as well, and it's invaluable. It outlines using the techniques and technicalities in an actual workflow. Good stuff and a great starting point.
Wouldn't the "Classroom in a book" series for AE be a good starting point? I'm slowly working my way through the Photoshop book now, and it's pretty straight-forward.
Just today I saw this book called, "After Effects and Photoshop: Animation and Production Effects for DV and Film." I don't yet have AE, and I'm in the same boat trying to find the best books to try to teach myself this stuff. (I hate doing this) The book seemed pretty streamlined for the purpose we all seem to want these programs for, at least as much as I can tell without knowing AE yet.