I've used both and I have to say that I learnt Premiere Pro, After Effects and PS using Lynda.com. What I particularly like is their exercise files so you can practice alongside the training videos - a dual monitor setup really facilitates this. I put the training video up on my second (25-inch) monitor, then have Photoshop running on my main (40-inch) screen and it is a great way to follow n' learn.
Their courses are very structured, ranging from 'Beginner', to 'Intermediate' and then on to 'Advanced', but their One-on-One series from Fundamentals, to Advanced to Mastery on Photoshop CS5 were simply amazing. I learnt how to turn portraits of my nephews and niece into Avatars (as in from the movie Avatar - blue face masks, liquify tool to increase their eyes and broaden their noses, along with masks for face paint etc.) which was fun.
I'd also recommend the Classroom In A Book series for Adobe software as a decent alternative as you get a DVD-ROM with a lot of extra stuff like project files, bonus chapters and video tutorials.