I have taken my share of underwater photos. White balance is certainly an issue, but so is depth. How deep were you for this photo? If you notice in the photo which you linked, the shark is very close to the surface. That means that the natural sunlight has filtered through less water than it would of at, say, 50 feet. The light gets bluer at depth because the natural light becomes progressively more affected.
I think the two biggest issues with underwater photos are the depth (i.e. light source to subject distance) and the distance to your subject from your camera (particles in the water degrade the image). So the best shots are, unfortunately, the ones you take at 3 feet under the water with the camera pressed against your subject.
A strobe on a a long arm is the best solution at depth, because that light has traveled through less water than the natural light from above. This lets you balance your subject against the blue of the background water.
All of this assumes that you did not take the above photo in an aquarium of course . . .
Hope that helps!