Cannot complete SSL handshake with one server from GCE Ubuntu 16.04.1 image (but works everywhere else)

I'm trying to connect to swift.ca-ns-1.clouda.ca:8443 via SSL. I can connect to this server from multiple other machines including other fresh 16.04.1 boxes (not on GCE), and I connect to it from other GCE instances that are not Ubuntu 16.04.1, but when I try connecting from any Ubuntu 16.04.1 GCE instance the SSL handshake fails. I've posted an example output from openssl below. Note that I can connect to every other SSL server I've tried. CloudA themselves couldn't figure it out. Any ideas?

% openssl s_client -connect swift.ca-ns-1.clouda.ca:8443
CONNECTED(00000003)
write:errno=104
---
no peer certificate available
---
No client certificate CA names sent
---
SSL handshake has read 0 bytes and written 305 bytes
---
New, (NONE), Cipher is (NONE)
Secure Renegotiation IS NOT supported
Compression: NONE
Expansion: NONE
No ALPN negotiated
SSL-Session:
Protocol : TLSv1.2
Cipher : 0000
Session-ID:
Session-ID-ctx:
Master-Key:
Key-Arg : None
PSK identity: None
PSK identity hint: None
SRP username: None
Start Time: 1475846555
Timeout : 300 (sec)
Verify return code: 0 (ok)
---

UPDATE: I've confirmed this only happens in the us-central1 zones (any subletter is also affected). Creating an instance in us-east1 works perfectly fine.

write:errno=104
...
SSL handshake has read 0 bytes and written 305 bytes

This means that

• the TCP connection to the server was succesful
• openssl s_client tried to start the TLS handshake by sending the ClientHello
• the server or some middlebox (firewall, load balancer...) caused a RST (errno 104 is ECONNRESET) of the TCP connection (probably) as response to the ClientHello

It is impossible to say from this information what caused the RST and what system has send it. But one can try to narrow it down with some experiments:

• Check that all 16.04.1 (working and non-working) use the same openssl version. Calling openssl version is not sufficient since distributions backport changes to older versions and the version number does not get changed. Use instead openssl version -a and compare the build time. If they are not the same make sure they are and test again.
• Check that you use the same IP address for the target on all systems, i.e. try to use s_client with a known good target IP instead.
• Check if the server has problems with the originating IP address by tunneling the connection (for example with OpenSSH) so that it originates from a known good system. If you are unlucky your systems IP address is on some blacklist because of activities of the previous owner.

I had similar issue. It was solved by adding servername option. For example if you are connecting to gmail: openssl s_client -connect imap.gmail.com:993 -servername gmail.com

See https://en.wikipedia.org/wiki/Server_Name_Indication for more details.