I've already looked, and I'm fairly confident that these services do not offer support for linux.
But I wonder how hard it would be for someone to use(read: reverse engineer or reprogram) a package manager like YUM , apt , or portage or etc to backup to servers?
They're already tuned to move data AUTOMATICALLY from one computer to another if there are any changes.(which is the big part) The part of unpackaging rpms or whatever is something that is an unnecessary function for this process.
All that would be required would be for you to setup a computer at a friend or relative's house.
I dunno about the backup-services you are mentioning, but afaik many of them offer linux-support. e.g. spideroak.com, ibackup.com (supports rsync!) and Amazon S3 (I think)
But I have no clue what you're talking about concerning package managers. Why would you want your package manager to do backups?
If it's backups at regular intervals you're looking for a cronjob (+rsync possibly) would be the tool for that.