This was the errors message:
PTY allocation request failed on channel 0
Searching around on the internet I found that there is a device ptmx that might be missing with this error message. SO I did the following:
[root]# ls -l /dev/ptmx
ls: /dev/ptmx: No such file or directory
[root]# /sbin/MAKEDEV -d /dev ptmx
and restarted sshd and Now everything works again!!