Shutter speed is always an issue with point-and-shoot cameras because they were built for topside use and have such small lenses. I have a S230 which is the older model to yours and I've enjoyed quite a few dives with it.
http://www.photoworks.com/share/shareLandi...566E1B90E&cb=PW
http://www.photoworks.com/share/shareLandi...151A28319&cb=PW
Here's 4 tips:
1.
UNDERWATER photography is not like EVERYDAY photography. The fact that you say that you don't shoot underwater very often says that you expect too much. It's very, very difficult (like learning photography all over again) But with practice comes better results.Those of us who've shot underwater using film know that you're lucky to get 1 good shot per roll! Digital cameras haven't made the success ratio any higher, they just allow you to see your failures faster. 
2. Don't zoom. For the largest aperture, the lense needs to be at its widest. This will allow the most light into your camera.
3. Try setting shooting in the 'MOUNTAIN' mode (the Macro button shifts you into 'flower' 'mountain' and 'normal' mode). I believe this forces the camera to focus at infinity (I'm not 100% on that). With the wide lense, this should still keep items further than say, 2m from you infocus (I'm not sure of the minimum focus distance of this camera underwater so you'll need to experiment).
4. If shooting in NORMAL mode. Try to pre-focus the camera by half-pressing the shutter at an object at the approximate distance to the your subject. This is the most tricky to get right.
OTHER CAMERA
As to your question about getting another camera with more manual controls. The Canon A85/A95 and S50/S70 offer aperture priority and shutter speed controls. I own a S70 and am quite happy with it (its a bit smaller than the A series cameras). I would recommend keeping your S400 as a backup camera in any case.
Again let me stress that no matter what camera you buy, when you shoot underwater, it takes a lot of patience and practice! 