Just to follow up - I've done a few quick tests on some snippets of underwater video to show what can quickly be achieved through levels correction. If you're lucky, something useful can be extracted from even very green footage (if you're not lucky it goes all horrible); and even reasonably well balanced footage can be spruced up a bit. All done quickly in Premiere 6.5. Originals on a Sony SC100 or PDX10.
One old sample that shows the principle very well (original at 15m in UK on auto white balance):
More at
Picasa Web Albums - David P - Misc - see captions for details.