Well, if you come from a graphic design background, I'm going to assume you're probably pretty familiar with Photoshop (or maybe Illustrator). This is a really great thing because you can think of After Effects as being like Photoshop + motion/time. They both use the same layer structure, blending modes, etc. The major difference (aside from working with video or keyframes or whatever) comes in the fact that nearly everything you do in AE is "non-destructive." For example, in Photoshop, if I take one of my layers, and I want to blur it, once I do, it's done. It's blurred. I can't adjust it from there without undo'ing. If I decided later on that I didn't want that layer blurred, too bad for me. I either have to remake it as it was before or undo all the other work I've done. In AE, I have a layer that I want to blur, I add the blur effect to the layer, and I can adjust the parameters of the effect as many times as I want, whenever I want. And where the TIME aspect comes in, I can keyframe those parameters over time.
I realize that you probably already know a lot of this stuff, but I just wanted to stress the idea that using AE isn't all that different from doing traditional graphic design, if you think about it in that aspect. As far as I'm concerned, learning how to animate is the easy part (I should say, easy to learn, hard to master). Learning to make a really compelling looking frame takes work and experience. And having a background in graphic design can only help you down that path (I really mean that. I work as a motion designer for a major post-production house in Chicago, and we've interviewed people in the past that have little to no experience in After Effects, but are amazing designers in general, because we figure it's easier to teach them to use AE then it is to teach them to make things look good).
Here's my advice. Really sit down and think hard about an idea you want to execute in your video. Don't think about what you'd use to do it and don't confine your ideas to things you already know how to do. Maybe it's as simple as, you're making a romance video about two characters and there's a specific shot you like, but one of the characters doesn't visually represent the mood you're trying to convey (ie; should be a happy scene, he looks angry). How would you go about changing the look of that in Photoshop? Got an idea on how you'd do it? That's a great starting point! NOW try and figure out how you'd make that work in After Effects, knowing the basics that you already know.
Say, knowing what all of the built-in effects do isn't really all that important if you don't have a good use for them. There's certainly nothing at all wrong with just going into a new composition, making a new solid and just throwing random stuff on it to see what it does. But when it comes to practical application, have a reason. I can't speak for the general audience, but for me, the videos that have always really impressed me with their effects-usage are ones where the effects served a greater purpose than just "make look shiny/bad ass" (not saying you're doing that. Just a general rule of thumb for me personally).
To answer your tutorial question, to be honest VCP is definitely the biggest game in town as far as AE tutorials go, but there's also good ol' standards like Creative Cow (though to be honest, only go there looking for technical help. The technical stuff they teach is legit, but they're just not great designers),
Malta Annon, &
AE Tuts.
And if you ever have specific questions about anything, please feel free to ask me

Good luck!