metalwheaties

BTW, I have no affiliation with Wuala. I just like it.

Do you know about http://www.wuala.org ? It's free if you share your disk space, it's redundant, and it's fast and easy. Backups, rsync, and regular file storage via a browser in a Java based client (runs everywhere I have tried) make this universally good. I never paid a cent to them, shared a couple of machines worth of 50GB of extra space that is up 100% of the time, and I have > 100GB of space available to me.

Linux backups are really easy: Wuala's client uses fuse to mount itself as a file system, so you can simply do periodic tar, or you can let their own backup mechanism back up your stuff to a special folder they maintain perfectly. You can get to your backed up files anywhere in the world via Wuala.com. This feature has saved me gobs of effort a bunch of times already.