Hi Promox,
Sorry to hear that you ran into this bug.
Were you using X2Go Client for Windows?
I reproduced it yesterday with X2Go Client for Windows 4.0.3.2-20150301. It appears that this occurs when the server does not have an ecdsa 256-bit key. Some Linux distros generate one by default, others do not.
The workaround is to generate such a key: sudo ssh-keygen -f /etc/ssh/ssh_host_ecdsa_key -N '' -t ecdsa -b 256
I think this is a bug in terms of how x2goclient uses libssh
-Mike#2