I'm no expert on this, but I find the color correcting options in After Effects to be surprisingly poor given how crucial color matching is for compositing.
After Effects is not a compositing program. It's primarily a motion graphics program, that has some compositing functionality built in. But it's really no more of a "compositor" than Premiere or Final Cut Pro, both of which also have some rudimentary compositing functionality. True, you can do quite a bit of compositing with After Effects, but that's not really what it's designed for, and its compositing workflow is pretty clunky compared to a true node-based compositor, of which Nuke and Shake would be examples.
Although getting back to these questions, none of these programs would really be great for color correction. Granted, you do have quite a lot of flexibility to do that in Nuke and Shake, butlike After Effects and Motionthese programs are oriented far more towards single shots than entire sequences.
Color is actually pretty good at what it does. It's a bit of an intimidating program at first, but once you come to terms with it it's surprisingly straightforward. If you can get a Quicktime and an EDL out of Premiere, you should be able to import that into Color. Transitions will be a bit of a pain if you work that way, unfortunately, since you'll only be able to correct both shots as a single clip. You'll have to export the clips for each transition with handles, then import them into Color, place them on the timeline, correct them, then export them back to Premiere to finish. The FCP7 <-> Color workflow is much slicker in this regard, but if you're in Premiere now you're probably stuck with it.
Of course, Resolve is quite good tooand free! I don't know if it has a great roundtrip workflow with Premiere, but if it does that's probably the way to go. Be forewarned, though: It's not an easy program to grasp. If you have any experience with color correction you can pick it up pretty quickly, but for the novice Color is much friendlier in my opinion.
Probably the best tip I can give to anyone interested in doing color correction is to really learn to read the scopes. The temptation is strong to "eyeball" things and just get them close enough, but you can end up screwing things up very quickly without a way of comparing shots using a standard reference for colors. The first project I did in Color, I had no idea how to use the scopes, and I found that what I thought looked good at the time really looked silly and cartoonish when I had finished the reel and came back to look at it. Once I learned to use the scopes properly, I was amazed at how useful they are: Given two completely different shots, you can get them about 90% of the way to matching each other just by looking at the scopes, without even seeing the shots!
Particularly useful is the vectorscope, which is the round one that shows you the color balance of the shot. Play around with the color wheels for a bit and note how moving each one (low, mid, and high) affects the color balance of the shot in the vectorscope. Pretty soon you'll be able to color match shots just by "feel" using primarily the vectorscope. It's a pretty cool feeling, and you'll find you're much faster and more confident with color correction once you're capable of doing so.