SkyDrive is quite good offering from Microsoft, I've not had downtime yet, but I just don't like the idea they scan my photographs for the old nudies! (Which apparently violate their TOS).
DropBox is for some reason a darling with some people on the internet, I think because they love Python. However they had a security oopsie, which I don't care how short it was for, wasn't adiquately explained to my liking as to how such a mistake could be made.
(More cynically, their reputation on "the internet" may be slightly inflated due to a very clever referral link scheme)
I've heard of the security issues with Dropbox so I always have any possible private/sensitive data encrypted in case the worst ever happened. (I use Dropbox because I have not found a alternative that just works)
If you would like to help me out and use my referral link (so you and I get some extra free GBs), it's https://spideroak.com/download/referral/049cbbf6bc2c2df3b005...
It's a more general piece of software, but combined with git-annex assistant and your choice of hosting provider(s), it lets you create your own cloud storage, so you have potentially no concerns over privacy[0].
If you're looking for fault-tolerance, git-annex lets you distribute this storage over an arbitrary number of providers easily, so you can get redundancy between an array of cloud hosting providers.
I've been using git-annex for several months now, and while it's still a work in progress, I haven't had any issues at all with it. It seems to be very reliable and bug-free; the main things being developed now are additional advanced features and an improved GUI interface, etc. For people already accustomed to using git on the command line, though, it should be a seamless experience.
[0] This depends on how much you trust Amazon/Rackspace/your colo/etc., but that's a separate level of trust altogether.