You said you had someone else create the new images. What technology did they use? Was it different from that used for the original images? What happens if you create an image using a different program, or another instance of the same program?
The only other distinguishing fact about the non-working images seems to be that they were created recently, and applied to categories that were created recently. Has there been any change in your hosting circumstances? (This is a total WAG, as I can't imagine how such a change could have an effect on these elements.)
you might try reopening a COPY of one of the images that does work (temporarily rename the original for holding purposes), save that copy and test it on your site.
Have you tried this? What happened (in as much detail as possible)?