Well, from the looks of it, your setup all supports the ssh2 protocols and cyphers, and because you have had success on your other machines, this should be something specific with this system
With all other things working, and other users being able to ssh to the box (I presume, or you would...