I'm a beginner with PS CS4 too, and I've been working through Martin Evening's book (linked to above) and think it's great; yes, it is in-depth, but beautifully structured to assist anybody from novice to professional.
I avoid Scott Kelby's books like the plague; I can't stand the man's purile attempts at humour and personality-cult approach to teaching; it's one thing making jokey anecdotes in a seminar, but not in a book, FFS! I get the feeling that he beleives there's something "hip" and "cool" (daddy-o) about the way he carries on, but he couldn't be more wrong. Have never understood why he gets recommended so often; probably coz he has so many books out there.