Have you tried, http://duplicity.nongnu.org/ ? It supports a lot of things to backup on including Amazon S3. From the features page,
Currently local file storage, scp/ssh, ftp, rsync, HSI, WebDAV, Tahoe-LAFS,
and Amazon S3 are supported, and others shouldn't be difficult to add.
rsnapshot isn't an actively developed project any more (last release 1.2.0 was in 2005). Duplicity is actively developed (May 2012 release) and you may want to take a look at that.
UPDATE: Duplicity supports full UNIX permissions -- http://duplicity.nongnu.org/duplicity.1.html
Duplicity incrementally backs up files and directory by encrypting
tar-format volumes with GnuPG and uploading them to a remote (or
local) file server. See URL FORMAT for a list all supported backends
and how to address them. Because duplicity uses librsync, the
incremental archives are space efficient and only record the parts of
files that have changed since the last backup. Currently duplicity
supports deleted files, full Unix permissions, uid/gid, directories,
symbolic links, fifos, etc., but not hard links.
s3 has object and bucket policies for read/write/update access that you configure for users and groups.