How can I trouble shoot a failing ssh connection?

If you have root access to the endpoint, the easy way to solve such problems is to run sshd in debug mode, by issuing a command like 

On the endpoint:

sudo `which sshd` -d -p 2222 on the endpoint

On the FlexDeploy Server:

if trying to connect using user/password

ssh -p 2222 user@host -v 

or if trying to connect using an ssh key with or without a passphrase

ssh -p 2222 user@host -v -i <private key file here>

Between the two outputs, you will probably be able to figure out what the problem is. Otherwise, send both logs in a support ticket.