I've been backing up all of my important machines to Amazon S3 using Duplicity for sometime now. It's worked out really well but required just enough hackery to prevent me from providing straight forward instructions for others.
I'm all about sharing the love so I submitted a new S3 backend to upstream using the excellent [boto] (http://code.google.com/p/boto/) library from Mitch Garnaat, and I packaged boto for Debian. The new backend made it into the 0.4.3 release of Duplicity, which in turn migrated to testing a couple of weeks ago. Now there is an Etch backport of 0.4.3 on backports.org.
In addition to installing duplicity from backports.org you will also need to pin python-boto from Lenny.