Just a quick note to mention how impressed I have been with my current backup solution, Bacula (using an Overland Neo2000 tape library, which also does the job nicely). A basic setup is pretty straightforward, and after that it runs smoothly and with very little need for intervention (other than tape switching. I have yet to find software that will pull the tapes out of the fireproof box for me & put them into the tape library…).
It handles very large filesets well - I need to do a restore of nearly 1TB of data next week, & initial dry run indicates that while it takes a *long* time to build the directory tree (lots of little files in that dataset, which doesn’t help), it will work OK. I understand that more recent versions are quicker (I’m running the version currently available in Debian etch, which is 1.38.11).
Smaller restores happen fast, and the restore interface is pretty usable. (I think there’s a graphical interface available; I use command-line style stuff).
Support is also excellent, with an active mailing list - the developer seems to spend a lot of his time answering questions there very patiently.
Might not be worth the setup time overhead if your backup requirements are small, but definitely well worth it for anything upwards of a couple of machines.