With Cloud computing, operators frequently have access to all your data. Sometimes it is part of their business model to use it (e.g. gmail). As long as you are aware of that, no problem. They typically won't use your data for things more harmful than targeted advertising (although you should check that ToS do not give them ownership of your data...), except if you're, say, a paedophile, in which case they might tell authorities (http://www.telegraph.co.uk/technology/news/11012008/Paedophi...).
In other words, your data is typically well protected as long as the cloud provider and entities which could require access to its data (e.g. law enforcement agencies from its home country or the countries where its servers are) are not part of your threat model.
And the "cloud" is just that: the servers you don't own and don't control. When some company mentions that they will store your data in the cloud, they could have just said that they are going to store your data on their servers. But for some reason "the cloud" sounds more trustworthy than "our servers".
I maintain that "the cloud" is a marketing term, not a technical one. There is no new technology here. There is no need for the term "cloud".
On the other hand, the internet was a new technology, thus the new term for it was justified.