Crumpler make a very nice range of soft bags, well designed and built.

My C725 fits perfectly, with an internal pocket for spare 4xAA batteries and
memory card.

They are pricey though. Lowepro make great bags too. Check our some camera
stores...