I think I saw your post in the Photoshop forum. Can you give us some details about your frame grabs. Like their pixel dimensions, and file type. Mine are 654 x 480 pixel PNG files. I used to have Vegas de-interlace them at the time of grabbing, using interpolation. Now I do that in Photoshop using the Photoshop Video-Deinterlace filter. That way I can see the effects of interpolating either the even or the odd fields.
Before I upsample (I currently use Genuine Fractals instead of PhotoZoom because I already have GF) I use a denoiser. I have Neat Image, but Noise Ninja or Picture Cooler would work just fine. It's best to do that before upsampling because upsampled noise is difficult to remove.
I suggest using the advanced PhotoZoom controls, and use very little, if any, artificial detail, unless you want a grainy effect. Decide what size in inches your magazine wants to print the frame grab and use that info to calculate the required pixel dimensions of your finished product. Hopefully they won't try to print your grabs too big, because they don't have a lot of image detail.