Ok, now the 0.5 release of my Simple Backup suite can now actually restore something from your backups! (both command-line and Gnome interfaces) It now even does automatic backups (and not just claims that it does). It even doesn't store empty folders in the backup. Oh and some usability fixes are also thrown in for no extra charge. :)
Note: due to a small, tiny bug in gnomevfs, restoring files from remote backup locations doesn't work yet. I'll have to do a lot of hacking to get that working :P