Without seeing the pics, I'm going to make an un-educated guess...
It may be that they're re-sizing the pics (even just slightly) rather than (or in addition to) simply cropping them, and their software probably sucks...
for example:
I have MGI photosuite on all my computers. I like the program because it's really simple and easy to use. However, re-sizing pictures, even by SMALL amounts, just totally messes 'em up! (ESPECIALLY for printing!)
Couple of tricks I've learned:
First, crop your pics YOURSELF, so they'll fit perfect at the size you want printed! ie: your 1600 x 1400 pics are at a 1.33 ratio, but your 4 x 6 prints are a 1.5 ratio...to make your pics 1.5 ratio, you need to crop the height down to 1066 pixels. (different "standard" pics all have different ratios; 8x10=1.25, 8x12=1.5, 5x7=1.4, 3-1/2x5=1.43)
second--if you want/need to downsize pictures, AND you have a photo program with any type of "screen capture" function (where it takes a "snapshot" of your computer of whatevers on the screen on any other program), then use Microsoft Word to re-size your pictures! Just use the "INSERT/PICTURE/FROM FILE" function, and insert the picture you want to re-size. Just click on the picture, and then you can size it up or down by dragging the corner--and you'll find that MSWord does NOT degrade the
picture as you resize it! (even down to thumbnail size!) Once it's the size you like, take a screen-capture snapshot of it, then finish it off!