I do my screen caps the same way I do my music videos... I rip the DVDs.
Once I've got all the VOBs that I want ripped, I go through them with DVD2AVI and create project files (in and out points in the video stream, usually by episode).
With these project files I write AVS (AVISynth) scripts. The scripts allow me to do things like inverse-telecine the footage, pretty damn well eliminating the interlacing. This gives me a fully progressive 23.976 fps video stream.
From here, I just go through in VirtualDub (a non-linear video editing program, mostly used for pre- and post- processing on video clips) and find the frame I want, do "Copy Input Source to Clipboard" (or something similar, forgot exactly how it's phrased), go to Photoshop, create new, and paste!
That sounds like a lot of work, but it actually allows me to go through and pinpoint the
exact frame I want, rather than relying on my timing to press the "Capture Screen" button, or whatever, in software DVD players or through the video card.
I prefer to do all my image editing directly in Photoshop, rather than letting any video filters do the work to the entire clip. That just slows down VirtualDub (and thus my CPU), and if it's just one frame (like it is with screen caps), I'll do it myself.
Once I've got the image pasted into Photoshop, I generally resize it from 720x480 (native DVD resolution) to 640x480 (the correct 4:3 aspect ratio), and then crop out the black borders. From here I'll usually adjust the contrast and color levels (generally letting Photoshop do the work by picking "Auto Contrast" and "Auto Levels," but taking over when I think I can do better

).
Once that's done, I'll usually do some type of "Smart Blur" on the image. Rather than manually fill in the colors, like you mentioned, Smart Blur pretty much does the same thing. It works WONDERS on skin tones, and usually does a good job with the rest of the image. It's a great way to clean up any macroblocking. You've gotta find a good balance between too little and too much blurring, though, because it ends up looking like water colors if you go overboard.
From there, resize to what I need it for (small for screenies like in the guides, or larger for whatever purposes), and do whatever else I need to do, like adding a border and drop shadow.
*gasps for breath*
Yeah, I'm an anal retard. But it looks nice!
The image in question, the Cell one... I did all of the above to. It actually didn't need all that much work, since it's a low-motion scene, which resulted in very little macroblocking. I
did blur the whites in his eyes a little bit, though, manually... kinda blocky, in there.