I played a bit with both and they both worked well.

Tarsnap: easier to set up and use Duplicity: fully open source, and I think the restore speed was significantly faster ... but I've not properly benchmarked it apples-to-apples.

If you are backing up a lot of frequently changing files (eg. database backups) then tarsnap's bandwidth charges (probably caused by the underlying EC2 charges) can swamp the storage cost. Running duplicity against rsync.net avoids this.