YEARS ago, when i studied design at university, most all the instructors highly recommended the BIBLE books. I've purchase several versions over the years for PSD, ILLY & InDesign. I like having them around for reference but i find that i have much better recall with video instructions. I'm not even sure the Total Training dvd are still around, but i loved those... a bit pricey though.
I also like Lynda.com and it a great deal at $25 per month subscription, as you can watch tutorials on all the software as often as you want. They are constantly updating and add new lessons and a really nice thing is that you are not committed for any particular length of time. you can buy a month, cancel the next and start up again whenever you want.
Really though, i like having many forms of instructions at my disposal. You just never know who is going to present a particular feature in a way the best sinks in... sometime i'll read or watch a tutorial over and over and still be like
... and then get the same info elsewhere and i think "well that makes perfect sense, why didn't the other guy just say that."