ccollect aims to do broadly the same task as rsnapshot but is written as a shell script instead of in perl.
Box Backup supports encrypted backups. It's written in C++ and requires a little more configuration than rsnapshot, but if you need its features it's the bees' knees.
rdiff-backup stores a full backup plus sets of diffs, so may be even more space-efficient than rsnapshot if you have frequent small changes in large files. This comes at the expense of not having several days worth of full backups instantly available.
duplicity is similar to rdiff-backup (not surprising considering it has the same author), but also supports encryption, so you can store your backups on an untrusted fileserver. It's not yet stable though.
Snapback2 is another tool very similar to rsnapshot. Of particular interest to rsnapshot users might be the 'snapcopy' utility for moving your snapshots from one filesystem to another, preserving all the hard links.