Get any decent cannon point and shoot camera (or if you have the budget, get a DSLR). It has to be a cannon because you can put additional software on these called CDHK - http://chdk.wikia.com/wiki/CHDK
Put a massive SD card in it, 4 gig, 8 gig, biggest you can get.
Put CDHK on the camera and set it up to do intervalic (time lapse) shooting, one shot every 1,2,5, whatever seconds.
Let it just take pictures and do not have the Arduino do anything.
If you wanted, you could have Aurduino control just the shutter by triggering the camera with 5V and a very easy to make cable, but you would need to have a way of seeing what the camera sees down there, which if you could do....you wouldn't need a camera to take photos down there, you could just frame grab the images coming up.
But let the camera do all the storage and photography, unless you are going to pipe it back up to the surface in real time, just retrieve the images off the camera when it comes up. Give the camera its own battery and let it live in its own world and let the Arduino drive the boat ...which is 400 feet below the water with your camera on it...and I assume you want to get both of them back.