OK, after doing a little more poking around this is what I came up with. I didn't have any problem with other images, they are not only saved just fine, but I can actually crop them without the same issue. So to double check, I went ahead and created some screenshots using ImageMagick's import in different formats (tiff, png, jpeg) and they all had the same problem after saving (if I cropped or not)! However, these same images (the original screenshots) displayed just fine in ever GNUstep image viewer: PhotoClip, ImageViewer, Preview and Yap (I know Yap uses a2ps, but I did it anyway). Because Yap doesn't use GNUstep, I was able to save all the images that were giving me crap on the pure GNUstep apps without a single glitch, so the problem is definately in GNUstep.
Appearantly ImageMagick does something with the image which makes GNUstep go crazy, but doesn't happen anywhere else.
I can reproduce this everytime! Should I go ahead and just file a bug report?