Here's what we've learned so far:

The issue is related to a new security feature that blocks TLS Fallback, which is a client that connects with one version of TLS, then tries to downgrade the connection and connect with a lower TLS version.. It was a feature made in light of the Poodle SSL vulnerability in order to keep SSL secure. The problem is that many networking libraries still exhibit this behavior of downgrading TLS versions on purpose, which OpenSSL then blocks the connection.

Specificially, the NSURLConnection class on iOS exhibits this behavior. NSURLSession, the latest iteration of this client, does not. The problem is, if you want to support iOS 6 still, you HAVE to use NSURLConnection. We decided to end support for iOS 6 because of this. NSURLConnection is also completely depracated in iOS 9, so if you want to support iOS 9, you'll have to upgrade your client library anyway.

On Android, the same thing happened, but not as often and between different TLS versions. Switching to Square's Retrofit client for SSL purposes has worked really well for us.

So, the real fix is to make sure you update your clients. If you're on a Debian wheezy box, you can make your own openssl package with the latest version, but with TLS_FALLBACK_SCSV support removed by following the directions below. Note, this is not recommended from a security perspective, but if your environment is broken, you need to do what you need to do. As long as SSL v3 is disabled, there's no big, active vulnerability in the wild that takes advantage of fallback at the moment.

Setup dquilt as shown on https://www.debian.org/doc/manuals/maint-guide/modify.en.html

Building Package:
apt-get update ; apt-get source libssl1.0.0
cd openssl-1.0.1e
dquilt pop Support-TLS_FALLBACK_SCSV
dquilt delete Support-TLS_FALLBACK_SCSV
dpkg-source --commit
dpkg-buildpackage

The debian packages will be one directory back. Make sure to install the libssl packages you created, not just openssl, and nginx will need a restart to use the new library, not just a reload.

I hope this helps someone, we spent a good amount of time on this.