"Connection to host lost" using telnet to MySQL
What you're seeing with the telnet test looks like normal behavior, since mysql doesn't "speak telnet," so the result may not be all that helpful... all it really tells us is that a TCP connection to the remote machine is at least possible.

sqlbot@dev:~$ telnet 10.20.30.40 3306
Trying 10.20.30.40...
Connected to 10.20.30.40.
Escape character is '^]'.
N
5.5.15-log|     \Q_l"`&gt;SÀh4e$~rA/b$'9mysql_native_passwordConnection closed by foreign host.

sqlbot@dev:~$


A better test would be to try the MySQL command line client -- from the same machine where you're getting the error from on workbench.  Whether that succeeds or fails will probably be more informative.

How long does it take for the message to appear?