Being an Adobe Illustrator user for 10+ years, I would suggest Lynda.com tutorials and two books.
Real World Adobe Illustrator
And
The Illustrator Wow! book.
These books are fast paced but provide in depth information on how to work efficiently with illustrator. You'll probably need something (like the lynda.com video tutorials) first to get you started.
Another thing, don't be afraid to get a book or video that was written for an older version of Illustrator. Try to stay above version 8.0 when selecting, but after that, they mostly just add features. Even the old learning material works just fine. A newer title is better, but not necessary.
One final note: Learn the shortcuts: Illustrator is one of the fastest programs. The key to it's power, speed and ease is that it's balance lies slightly more in the keyboard shortcuts over the mouse. Browse through the WOW! book and check out the "finger-dance" section. Advanced illustrator users find this technique necessary.
Illustrator is amazingly versitile and powerful. It is absolutely my favorite application ever of all applications that I own. It's the single most-used program on any of my computers. But like I said, the key to illustrator is the finger-dances. Learn those and you'll be illustrating at least 5 times faster, if not more.
Good Luck.