Some images defy one-time correction due to wide variations in lighting or color temperature.  Lighting issues are common with wide scenes that include clouds, ocean surface, or a mixture of natural light and flash.  Over-under images are especially troublesome.  The best way to tackle these problems are to make at least two copies of the original image, adjusting each copy to address one problem, and blending them to create your perfected image.  DSLR users shooting RAW will reap the greatest benefit using this method.

First copy corrected for realistic coral & water

Second copy corrected for realistic sky 

Sky layer pasted above water layer

Eraser tool used to 'wipe' away unnatural green areas, leaving sky visible

Two layers are merged to create final image