I have an A40 and a friend has the coolpix 3100. So far I can't fault the A40 other than it's only 2MP (A70 is 3MP) and with four batteries can be a bit heavy for a pocket camera.
You are right about battery issues on the coolpix. We went hiking in the peak district the other week and my friend took a pack of duracell's as back-up. When they were put in the camera wouldn't even switch on so I gave him two of my rechargables and I used the duracell's in my canon.
The canon can also be fitted with add-on lenses but the coolpix comes with a charger and Adobe Photoshop Elements. You'll need to buy a seperate charger for the Canon (£15 charger + 4 1700ah batteries from Maplin).
If it were my money I'd go for the Canon with batteries and charger from Maplin and two 128mb CF cards from Crucial.co.uk (about £50).