There may be more going on here than meets the eye. Looking at your "after" crop, I suspect you may have a lot of JPEG artifact. Try setting your camera to its highest quality mode, take a shot, set it to a low quality mode, take the same shot, then try increasing contrast of both. You should see much smoother results with in the highest quality mode. Noise and JPEG artifact tend to be very noticeable in blue sky.
By the way, I tried adjusting contrast of your crops in Photoshop 7, the results are just as bad as in your editor. I've also tried neatimage and found that for many (not all) images it produces pretty good results.
A final note, when re-saving images, its best to work in a non-lossy format like .TIF. If this is not convenient, save as JPEG at very high quality until the last step, then tweak compression to achieve the smallest file size that produces acceptable image quality.