I am running Ubuntu 10.10 on a remote box. I ssh to it everyday without issues but today out of the blue, I get the following error:

ssh_exchange_identification: Connection closed by remote host

If I connect with -vv, I get the following:

OpenSSH_5.6p1, OpenSSL 0.9.8r 8 Feb 2011
debug1: Reading configuration data /Users/bla/.ssh/config
debug1: Applying options for ubuntu-server
debug1: Reading configuration data /etc/ssh_config
debug1: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to ubuntu-server.com [123.123.123.123] port 22.
debug1: Connection established.
debug2: key_type_from_name: unknown key type '-----BEGIN'
debug2: key_type_from_name: unknown key type '-----END'
debug1: identity file /Users/bla/.ssh/id_rsa type -1
debug1: identity file /Users/bla/.ssh/id_rsa-cert type -1
ssh_exchange_identification: Connection closed by remote host

If I remove the key, I get the exact same output (sans "debug2: key_type_...). I've managed to log in physically and checked my hosts.allow and hosts.deny but they have no entries. I tried removing and reinstalling OpenSSH, checked authorized_keys and ~/.ssh permissions and tried connecting from other computers only to get the same error. I'm at my wits end, any help would be greatly appreciated.