is rsnapshot doing something different to usual: have you got a lot more files in your backup? is it now having to delete old snapshots, whereas before it hadn't hit some critical threshold? I found it to scale very poorly when I was using it. rdiff-backup is almost a drop-in replacement and doesn't suffer the same problem (lots of work to adjust large hard link trees)