As I was thinking about clipping, I realized there is an easy way to fix the hue of the sky in the GIMP (or Photoshop). To try it out, I used the following picture. I took this in bright sun on a Texas flight line in the early afternoon. I used fill flash to deal with the harsh shadows. This is the original, which was was not overexposed or clipped.
So why would someone use a correctly-exposed photo to illustrate a way of correcting clipping? So he would know the right answer. To do this on a photo that was originally overexposed, you can use all the same steps, you just have to play with a couple of things until they look right. To clip the colors, I moved the top point of the value curve in the curves tool from (255,255) to (191,255). Using the levels tool should give the same result. This provides the overexposed, clipped image.
I can now correct the overexposure by moving the top point of the value curve in the curves tool from (255,255) to (255,191). This step is optional, and if this was a real overexposed photo, you would have to figure out how far down to adjust it. Here it helps make the final result look more like the original. You can see that the hue of the sky is greener than it was in the original.
This is the real trick to this fix. I created a new transparent layer and used the brush tool to fill the sky with a color of the right hue (210). Only the hue matters. In a real situation, you would have to figure out what hue the sky should be, but an average of the bluest section of the sky should be close. If all of the sky is noticeably clipped, just pick a blue you like. You can color over the clouds because hue does not affect white or gray.
Next I changed the mode of the new layer from Normal to Hue. This makes everything below that layer have the hue of that layer. Clever, huh? The result does differ from the original in some important ways. The detail in the clouds is gone, and now they look flat. There is no way of fixing that, unless you want to paint them by hand. The sky looks a little different, but at least it now looks fairly natural.
It is better not to overexpose your photos, but if you do, this might help you deal with a cyan sky. Maybe next time Nathan will think twice before he asks a question about one of my pet peeves.