The error is exactly as here: [X2Go-User] X2Go Client: Kex error : no match for method server host key alog: server [ssh-rsa], client [ssh-ed25519]



However, I have some more information which suggest the server isn't the culprit.
When I use the current Windows client on a LAN, I get in OK. When I use the same from linux on the LAN, I get in OK. It's only when i've tried to port forward 2249 -> 22 from the WAN that it fails with this message from either client. Even stranger, if I SSH in from the WAN on port 2249 I get in OK. So the usual suggestions of regenerating keys etc don't seem to help, even though I did that anyway.

Server I'm trying to access is Ubuntu 16.04.3 
root@mojo:~# x2goversion
x2goagent: 3.5.0.32
x2goserver: 4.0.1.20
x2goserver-extensions: 4.0.1.20
x2goserver-xsession: 4.0.1.20
root@mojo:~#

Linux and Win clients are 4.1.0.0

Here's the last twist - this is a VM. I have also port forwarded 22 to 22 on the host, which is Fedora 26 and the main server actually running these VMs (KVM), and that lets me in via X2Go no problem. So the router itself can work if it's not going to a VM. I also tried disabling the firewall on the VM but still got no joy. At that point I knew I was plumb out of ideas so came here ;-) Thanks.