This is a tough one. I know that many people are keen on Learning Perl, but I had a bit of difficulty with it. I felt that some sections (hashes and regex) needed more robust examples before I felt I had a hand on them -- don't tell merlyn :). These are so basic to Perl that I felt they needed a more in-depth discussion. Of course, none of the languages that I had worked with prior to Perl supported either of these, so it may be a case of my being an idiot.

Perl: The Programmer's Companion is an excellent book, if you have plenty of programming experience under your belt. Also, Chapman's constant use of use English; makes common operators like $_ very unfamiliar to people to haven't used it before. (Yes, I took that straight from a review, but I also have the book and agree with that review 100%)

If you'd like to research books for yourself, check out some book reviews by Tom Christiansen.