Já considerou o CrashPlan? Eles suportam Linux (eu estou executando do meu servidor Ubuntu 14.04) e eles oferecem armazenamento ilimitado por um custo razoável. Se você está nos EUA, eles também têm a opção de enviar um seed drive para que você não tenha que fazer upload de 1 TB de backup inicial.
Eles têm duas opções de criptografia, uma em que a senha da sua conta é sua chave de criptografia / descriptografia, outra em que você tem uma chave de criptografia / descriptografia separada. Não funciona bem com criptografia local do que eu posso dizer.
Eu tenho usado nos últimos 5 anos. Não tive problemas com backups ou restaurações.