I use Slicehost for my VPS needs and am generally very pleased with them.
They charge $12.50 per month for their backup service. It seems like the system has been designed to be idiot proof. In their own words:
Backups are offered as an add on service and priced according to Slice size. They give you the ability to automatically run a backup without disrupting the system. At any given time, you have access to 3 images of your system: a daily (less than 24 hours), a weekly (less than 7 days) and a snapshot (variable). Monthly pricing is $5/$7.50/$10/$12.50/$15/$22.50/$30 for 256/384/512/768/1024/1536/2048 slices.
This seems OK, but I feel like I could benefit from a bit more control (especially with respect to content and timing). I also suspect that a 3rd party might be able to beat them on price.
An option I did consider was rsync
ing the filesystem to another machine/image. This seems like a more involved process than I'd like, but I'd happily consider it if it were significantly less expensive.