The church probably had fewer colors to begin with.
Sky is usually a lot of variations of one color. When color depth is reduced, it tries to match each pixel to the closest color in it's pallet. Typically for converting sky that would be trying to map 1000 blended shades of blue into just a few shades for a gif. In the reduced color depth version, you'll see patches of one shade or the other depending upon the luminesence and other factors for that area in the original.
It also helps to look at the pic in the lowest screen resoulution you expect your users to use. Jpgs that look fine on my 1600x1200 screen with the tiny tiny pixels look like trash on an 800x600.
I can check it out Monday evening if you can wait that long, other wise perhaps one of the other folk can help.