My first guess would be that the Clips on the Timeline are using non-square pixels, i.e. PAR = something like 0.9 for NTSC Standard, and you are viewing in a program that does not accept PAR other than square pixels, i.e. PAR = 1.0.
Now, some programs, such as Photoshop (CS or later) and maybe PSElements (?) can adjust the PAR of an image.
For more detail on PAR in Video (and in Stills from that Video), see this ARTICLE.
Which method are you using to output them? Unfortunately, Adobe has set the program up to only export freeze frames with non-square pixels.
In my books, I show you how to create a permanent preset for outputting your stills with square pixels.
Basically, you go to Share/Computer/Still Image and click the Advanced button. On the Advanced panel, you set your photo up as a 640x480 (you'll need to unlock the constrain preference by clicking on it) or whatever (depending on the specs of your original video) and set the Pixel Aspect Ratio up as 1.0 Square Pixels.