OK, I looked at the two gallery enlargements for those two examples and see they are both at about 400px x 300px. That's from mouse-over of each and using right-mouse click and properties.
What is the exact pixel dimensions of each stored image as original? I'm curious of one of two possibilities: 1) Auctiva is sending the stored 400 x 300 picture for gallery, or 2) the store image is in 4:3 aspect ratio and 400 x 300 is essentially the correct size for the 400 x 400 maximum allowed, i.e. the width of 400 assumes the maximum and the 300 is maintained by the aspect ratio of the photo.
I looked at a few that you apparently resized to 400 x 400 and they look stretched (to fit height). If those pictures were created at 1:1 aspect ratio, then that blows my theory. Checking the stored height and width of those photos in your image library should help resolve the issue.
Danno
Update: I checked the photo used in the first example listing and its original image is indeed at 4:3 aspect ratio:
http://img.auctiva.com/imgdata/8/5/4/7/8/0/webimg/181076704_tp.jpg (properity is 395 x 300)
The _O original stored image is at 883 x 671.
I would recommend you create those composite photos at 500px x 500px (square photo / 1:1 aspect ratio) for both the Gallery Plus and the new header pic standard of the New Design listing standard.
Danno