Do you know how to "slice" an image?
Thats when you cut the image into sections then you save each part of the image (section) as a seperate gif file.
If you know how to use the slice tool try slicing the image yourself and replacing the current sliced one with your edited file, this normally works better than trying just to cut out the parts you have to replace and keeps an even feel thoughout the image
If you dont know how, just say and I will try get you a tutorial