Of all of the potential shortcomings of the cloud, trust is perhaps the largest. "Seeing is believing" is a truism that certainly applies to IT. Although you could have the worst-run internal IT shop ever, there's a comfort in being able to walk down to the data center and put your hands on what makes it tick. Moving critical pieces of your application infrastructure into the cloud removes that (sometimes false) sense of security and leaves many people feeling exposed.
Of course, that's completely natural -- any time you trust anyone to do anything for you, you are exposing yourself to risk. If a provider tells you it's taking nightly backups of your cloud-hosted ERP application and it turns out not to be true, you're the one who'll suffer in the event of a failure. The same is true with a traditional IT department, but at least you can wander down and ask to see tapes and backup logs if you're concerned that your people might not be on the ball. That's not so easy to do when systems might be hosted hundreds or even thousands of miles away in a nameless data center and you're customer No. 20,000 out of 100,000.
From the cloud provider's perspective, this lack of trust is a tough problem to solve. Assuming you're doing a thorough job, how exactly do you get a potential client to trust your operation well enough to give you its business? Aside from having a good track record with existing clients that might recommend you, publishing audit reports such as SAS-70, SOC-1 (aka SSAE 16), SOC-2, and SOC-3 has been a great way to go about instilling that trust by having an independent third party vouch that you're doing what you say you're doing.