I started with the DC500 with strobe & WA, an earlier version of the DC800. Took about 5,000 pics with it, all UW. Then I went to a Nikon P5100 plus Ike housing & Ike strobe. Recently added a second Ike strobe. My wife, a good land photog, has an extra D70 that I may take UW soon.
Assuming that you don't want to spend the big bucks for a SLR, I'd definitely go with Nikon P5100 or 6000 or the Canon G9 or G10. They give you the ability to shoot in manual which is absolutely necessary UW, IMHO. The strobes are also essential for decent color. The Sealife camera is a nice starter camera, but you'll want more control as you get experience.
You can get used rigs on Ebay for both the P5100 & G9 now that the newer versions are out and save some serious bucks.