We don't know what your Premiere Sequence Settings are, or the resolution of the photo. If Premiere is scaling the photo, then you may get better results if you resize the image in Photoshop to match the video resolution, so no scaling happens in Premiere (don't overwrite original image, save a copy!).
Also, right-click in the Program Monitor window and see what FIELDS are set to, experiment with different options. Note that jaggies may be more apparent when paused - how are edges while playing sequence?
Safe Harbor Computers
My problem is actually more involved -- trying to mix HD and SD in Premiere. Pursuing the sequence settings issue, I did discover that a sequence can be created to match exactly the dimensions of the picture, which helps.
Ok, but typically you'll want to stick with standard VIDEO sizing (SD, 720 or 1080), and conform the STILL to fit, not the other way around or it is going to mess up your delivery having a non-standard frame size. What is the intended delivery medium? That will help determine the best sequence size to work with