Definitely a job for Photoshop. It's worth taking the time to try what Benny is suggesting. Check out the "Refine Edge" button in the toolbar after you've made a selection with the Magic Wand or Quick Selection tool.
Even easier and more artistic/fun if you've got a Wacom or some sort of touch surface to work with and paint in the colors by hand. There is a ton more flexibility with brushes and paint workflow in PS than AE, plus it'd be a good bit quicker once you've got it down.
Also Brian's suggestion of Auto Trace in Illustrator can make for some nice looks too.