Originally Posted by mortenb

Ok. Didn't see that one. Then it is without a doubt a DNS issue. And if you haven't played with your DNS settings it is with 99% certainty on the host site. Your ISP is that last 1% and since you can connect fine to other servers, that 1% is almost eliminated.
Have your host go over the reverse DNS again as Rowan suggested.

Try having them run sshd in debug mode (-d) while you try logging in