The root cause of the error in the title is due to Guacamole only supports ssh-dss and ssh-rsa, and both have been disabled in Ubuntu.
DSS was removed 8 years ago and it seems from my quick google that RSA has been deprecated, so hopefully Guacamole updates sometime soon.
In the meantime a workaround is adding HostKeyAlgorithms +ssh-rsa to the end of /etc/ssh/sshd_config on the Ubuntu machine and restart sshd.
Note: Please use at your own risk
