"Cloud-based" Internet services rely on the availability and reliability of managed data centers. Recent events indicate that data centers tend to create centralized points of failure, and providing resilience to large-scale faults remains a significant challenge for both providers and users of cloud infrastructures. Running data centers also incurs high hardware and network costs, particularly for storage-intensive applications such as data synchronization and backup. In this paper, we show how to improve data availability while reducing costs in storage clouds, by augmenting centralized clouds with an efficient client-side storage system. We introduce AmazingStore, a low-cost cloud storage system that provides high data availability while protecting against correlated failures. We describe our initial experiences with an already deployed prototype and outline opportunities in this modified cloud model.