One option is Tarsnap (http://www.tarsnap.com/), which is developed by HN's cperciva (http://news.ycombinator.com/user?id=cperciva). It's specifically written to be secure online backup.

Another option is using Dropbox, but with some kind of encryption. I know that some people use Dropbox to store TrueCrypt volumes, and I think it does an okay job with them.

Downsides to both are that you're not likely to be able to access them from a phone. Tarsnap also has no GUI (and requires Cygwin to work on Windows), which may be a consideration.