Anyone has experience with Duplicity?
http://duplicity.nongnu.org/
It's a decent tool. I encrypt with a separate gpg key, do mostly incremental backups, and a full one every few months. Incremental backups take under a minute on my desktop (100K files, 11G). Full ones are kind of slow (which is why I set it to only do it every few months).
I haven't used the S3 support.