My guess is that the resolution of those still pictures is very low, since the camera was made to capture images for viewing on another media. If that's the case, there isn't much you can do, because you can't create digital information that isn't there. You might experiment with some incremental upward resampling. (Work on a copy!) Open the image, and then go to Image>Resize>Image Size. Check "Resample" and gradually increase the resolution by about 10% per resample. Or, in the box next to the dimensions, set it to 110%. (I think - I usually do it manually.)
There are also a couple of third party apps that purport to doing a good job, but the latest information I've gotten indicates they really don't do any better than incremental changes through Elements. If you want to experiment, though, an application called Genuine Fractals has a limited-use demo available for download. Do a Google search for the site.