Questions-->> What are the file types and if, what kind of transparency is applied to them? And when you say you have several images for the background, how are you going about doing that? CSS/div background? Sorry but since the links are not allowed you will have to explain it out.
The only thing I can think of is that maybe the previous versions of the images were not all "Save For Web"? Did you just do a "Save As" the first time? If so you have no control over the optimizing part.