well, the problem is going to be at the other end, obviously
Do you have console access to the box? If not, then talk to somebody who does so they can have a look at it for you. It'll probably tell you exactly what is wrong in /var/log/auth.log , or the generic syslog file... probably some small config change somebody made without testing and forgot about