[CentOS] ssh_exchange_identification: Connection closed by remote host

Greetings,

I have accounts on two Centos servers, A and B, each hosted on a remote
VPS by a different provider/datacenter.

Until yesterday night, I could connect without problems via SSH to both
servers from my home Fedora 16 desktop.

Yesterday I completed (fingers crossed) the switch to a different ADSL
provider. From the moment I turned on the modem on the new ADSL line, I
became unable to ssh into server A. All attempts abort with this message:

ssh_exchange_identification: Connection closed by remote host

I know that server A is still up and running, because the websites and
email services it runs are still up. Server B is still reachable via ssh,
no problem. The only difference between the two servers is that A runs
Centos 4.something, while B runs Centos 6.1

I have already done some online search on this problem, but all the pages
I have found discuss how to diagnose and fix it working on the server (*),
which is exactly what I can't do right now...

Any clues on what may have happened, and if it could be related in any way
to differences (whatever they may be) between ADSL providers, instead of a
bizarre coincidence?

Of course, I can and will ask the VPS provider to reboot the machine, but
I would also like to know your opinion on what exactly may have happened,
and how to prevent it in the future (also to pass your suggestions to the
provider).

TIA,
Marco

(*) except remove the server entry from .ssh/known_hosts in my home
desktop. I did it and nothing changed