Denied write access for ssh encrypted backup.

Hmm. That's a bit strange. You have write permission on remote host because BIT already tested that before (would have been a different error msg otherwise).
Can you please reboot and/or make sure /tmp/backintime is deleted and try again? Also please try to set up a profile just with SSH without encryption. If you still get this error please run 'backintime-gnome' or 'backintime-kde4' from commandline and post the output after the error happened again.

Setting it up without encryption worked, but I would prefer to use encryption

Sure. This was just to see where the problem is located. Now we will work to get encryption up and running :-)

Please rename'.encfs6.xml' inside your remote folder (or remove it if you don't yet have anything inside that encfs container) so BIT can create a new one. And post the output from commandline please.

For some reason, ssh just stopped working. I rebooted the server after installing updates(ssh wasn't one of them) and now it refuses to check ssh certificates. It asks for my password. This is a problem outside of BIT though.

Please try out these steps:

1. Run 'test "x$SSH_AUTH_SOCK" = "x" && eval "$(ssh-agent)" ' to make sure ssh-agent is runnig

2. Remove your public key from ~/.ssh/authorized_keys on remote host (or remove that file completely if there is only that single key inside). Then you can set up the key again with 'ssh-copy-id -i ~/.ssh/id_rsa.pub USER@HOST'.

3. Run 'ssh -vv HOST@USER' and post the output in here

I removed my public key from the remote host, generated new keys, and copied them. SSH still doesnt work. I ran ssh -vv and this is the output.

OpenSSH_6.6.1, OpenSSL 1.0.1f 6 Jan 2014
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to 10.8.0.1 [10.8.0.1] port 22.
debug1: Connection established.
debug1: identity file /home/aaron/.ssh/id_rsa type -1
debug1: identity file /home/aaron/.ssh/id_rsa-cert type -1
debug1: identity file /home/aaron/.ssh/id_dsa type 2
debug1: identity file /home/aaron/.ssh/id_dsa-cert type -1
debug1: identity file /home/aaron/.ssh/id_ecdsa type -1
debug1: identity file /home/aaron/.ssh/id_ecdsa-cert type -1
debug1: identity file /home/aaron/.ssh/id_ed25519 type -1
debug1: identity file /home/aaron/.ssh/id_ed25519-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.6.1p1 Ubuntu-2ubuntu2
debug1: Remote protocol version 2.0, remote software version OpenSSH_6.6.1p1 Ubuntu-2ubuntu2
debug1: match: OpenSSH_6.6.1p1 Ubuntu-2ubuntu2 pat OpenSSH_6.6.1* compat 0x04000000
debug2: fd 3 setting O_NONBLOCK
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: kex_parse_kexinit: <email address hidden>,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: <email address hidden>,<email address hidden>,<email address hidden>,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,ssh-ed25519,ssh-rsa,ssh-dss
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,<email address hidden>,<email address hidden>,<email address hidden>,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,<email address hidden>
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,<email address hidden>,<email address hidden>,<email address hidden>,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,<email address hidden>
debug2: kex_parse_kexinit: <email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,hmac-md5,hmac-sha1,<email address hidden>,<email address hidden>,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,<email address hidden>,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: <email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,hmac-md5,hmac-sha1,<email address hidden>,<email address hidden>,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,<email address hidden>,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,<email address hidden>,zlib
debug2: kex_parse_kexinit: none,<email address hidden>,zlib
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit: first_kex_follows 0
debug2: kex_parse_kexinit: reserved 0
debug2: kex_parse_kexinit: <email address hidden>,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ssh-ed25519
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,<email address hidden>,<email address hidden>,<email address hidden>,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,<email address hidden>
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,<email address hidden>,<email address hidden>,<email address hidden>,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,<email address hidden>
debug2: kex_parse_kexinit: <email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,hmac-md5,hmac-sha1,<email address hidden>,<email address hidden>,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,<email address hidden>,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: <email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,<email address hidden>,hmac-md5,hmac-sha1,<email address hidden>,<email address hidden>,hmac-sha2-256,hmac-sha2-512,hmac-ripemd160,<email address hidden>,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,<email address hidden>
debug2: kex_parse_kexinit: none,<email address hidden>
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit: first_kex_follows 0
debug2: kex_parse_kexinit: reserved 0
debug2: mac_setup: setup <email address hidden>
debug1: kex: server->client aes128-ctr <email address hidden> none
debug2: mac_setup: setup <email address hidden>
debug1: kex: client->server aes128-ctr <email address hidden> none
debug1: sending SSH2_MSG_KEX_ECDH_INIT
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ECDSA 98:9e:8f:64:29:a9:6d:54:55:9a:84:67:b0:b6:79:8e
debug1: Host '10.8.0.1' is known and matches the ECDSA host key.
debug1: Found key in /home/aaron/.ssh/known_hosts:1
debug1: ssh_ecdsa_verify: signature correct
debug2: kex_derive_keys
debug2: set_newkeys: mode 1
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug2: set_newkeys: mode 0
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug2: key: /home/aaron/.ssh/id_dsa (0x7f337d208640),
debug2: key: /home/aaron/.ssh/id_rsa ((nil)),
debug2: key: /home/aaron/.ssh/id_ecdsa ((nil)),
debug2: key: /home/aaron/.ssh/id_ed25519 ((nil)),
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering DSA public key: /home/aaron/.ssh/id_dsa
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey,password
debug1: Trying private key: /home/aaron/.ssh/id_rsa
debug1: Trying private key: /home/aaron/.ssh/id_ecdsa
debug1: Trying private key: /home/aaron/.ssh/id_ed25519
debug2: we did not send a packet, disable method
debug1: Next authentication method: password

> debug1: Offering DSA public key: /home/aaron/.ssh/id_dsa
> debug2: we sent a publickey packet, wait for reply
> debug1: Authentications that can continue: publickey,password
> debug1: Trying private key: /home/aaron/.ssh/id_rsa
> debug1: Trying private key: /home/aaron/.ssh/id_ecdsa
> debug1: Trying private key: /home/aaron/.ssh/id_ed25519
> debug2: we did not send a packet, disable method

The remote host doesn't accept your key. I once had the same problem which turned out to be a permission problem. OpenSSH is quite picky with these permissions (for a good reason)
Please run this on your remote host:
chown $USER:$USER -R ~/.ssh
chmod 700 ~/.ssh
chmod 600 ~/.ssh/authorized_keys

I tried the permissions, and nothing changed. I still have to enter my password every time I connect via ssh. I ran it with -vv and got the same output as before. I've tried generating new certificates, restarting ssh, checking all of my settings in sshd_config, and nothing is working.

Please change 'LogLevel' to DEBUG in /etc/ssh/sshd_config, restart sshd and take a look at /var/log/auth.log after a new failed login.

Sep 6 14:38:25 server sshd[13799]: debug1: trying public key file /home/me/.ssh/authorized_keys
Sep 6 14:38:25 server sshd[13799]: debug1: Could not open authorized keys '/home/me/.ssh/authorized_keys': No such file or directory

Those were the two lines that show the problem. The other lines clearly show that the server gets my dsa key, attempts to check it with the authorized_keys fiel, but the authorized key file is not found. I'm 100% sure it's there, through cd, ls, and nano. I tried the permissions but that didn't change anything.

Can you try to delete ~/.ssh and recreate it (with ssh-copy-id)? Maybe authorized_keys is somehow corrupt.

Sorry, there is nothing more I can help you with. Maybe you should ask in special Linux Forum where the guys have more knowledge of ssh than I have :-)