I just bought Adobe Premiere & Photoshop Elements 11 and I'm trying to do the following:
I'm trying to make a version of a video where everything but the desired objects are masked/painted over with green.
The method that I've chosen is to break the entire video up into individual frames and paint over in every frame the desired green screen effect (600+ of them). Once I'm done, I'll add them all back together in order in Premiere, add the audio, and have myself an identical clip with green screen.
This method may turn out to be very tedious and I was wondering if there is a more efficient way of doing this?
Yes. You should actually SHOOT your video in front of a well-lit green screen in the first place. That's the way the pros do it.
You're definitely doing it the hard way -- but, if your initial footage wasn't set up for green screen in the first place, it's the only way. (In fact, you're doing it the way the pros do it when they, for instance, want to take footage of Clint Eastwood from "Dirty Harry" and make it look like he's standing in the crowd of a movie shot this year.)
I do cover working with Chromas Key and Green Screen key in my books, if you're interested.
The creation of "green screen" from footage, not shot that way, is a very intensive process, called RotoScoping, or basically the method that you employed. However, Adobe After Effects, as of CS 5, has a neat new Tool, the RotoBrush, that makes the job easier. See this tutorial for more info on the AE RotoBrush Tool: http://blogs.adobe.com/aftereffects/2010/04/roto-brush-in-after-effects-cs.html
As Steve points out, shooting green-screen is the best way to do it, and this article will list some good green-screen resources: http://forums.adobe.com/thread/568419?tstart=90