GD is fairly horrible for scaling images (great for generating them as it is), give Imager a try; while it won't solve your current problem (which we can't really say anything about without seeing the code), it will give you an allaround more pleasant time manipulating images.

Supposedly Image::Magick is good for this sort of thing too, but personally I haven't been able to get it to install (and didn't have time to wrestle with it), Imager, on the other hand, needs no bulky external libraries.