Android SSL handshake succeeds on Genymotion virtual device fails on physical device

Question

My Android app uses TLS to talk to a remote server. For some reason the TLS handshake succeeds when I run my app in Genymotion virtual machine but fails when I run it in a physical phone device.

Looking at the traffic with Wireshark I see the following exchange (server messages are indented):

TLSv1 Client Hello
TLSv1   Server Hello
TLSv1   Certificate
TLSv1 Certificate
TLSv1 Client Key Exchange

sslv3 Client Hello
sslv3   SSLv3 Record Layer: Alert (Level: Fatal, Description: Handshake Failure) (40)

Based on my reading error 40 is this may be because of lack of agreement on a common Cipher Suite:

http://support.citrix.com/article/CTX124731

Upon investigation it seems that server only supports a single Cipher Suite:

Cipher Suite: TLS_RSA_WITH_AES_128_CBC_SHA (0x002f)

It appears that the TLS_RSA_WITH_AES_128_CBC_SHA is not supported in SSLv3.

What seems odd is why does the handshake start over using SSLV3 protocol with a second Client Hello?

In the successful scenario involving Genymotion Virtual Device the message exchange was as follows:

TLSv1 Client Hello
TLSv1   Server Hello
TLSv1   Certificate
TLSv1 Certificate, Client Key Exchange, Certificate Verify, Change Cipher Spec, Encrypted Handshake Message
TLSv1 [TCP Retransmission] Certificate
TLSv1 [TCP Retransmission] Client Key Exchange
TLSv1 New Session Ticket, Change Cipher Spec, Encrypted Handshake Message

****Update*****

I changed app code to force TLSv1 handshake without any fallback to SSLv3 using the following code snippet:

    SocketFactory sf = SSLSocketFactory.getDefault();
    SSLSocket socket = (SSLSocket) sf.createSocket(host, 443);
    socket.setEnabledProtocols(new String[]{"TLSv1", "TLSv1.1", "TLSv1.2"});
    socket.startHandshake();

This showed the following in wireshark:

TLSv1 Client Hello
TLSv1   Server Hello
TLSv1   Certificate
TLSv1 Certificate, Client Key Exchange, Change Cipher Spec, Encrypted Handshake Message
TLSv1   Alert (Level: Fatal, Description: Handshake Failure)

The Alert message details look like this:

+Secure Sockets Layer
  +TLSv1 Record Layer: Alert (Level: Fatal, Description: Handshake Failure)
    +Content Type: Alert (21)
    ...
    +Alert Message
      Level: Fatal(2)
      Description: Handshake Failure (40)

I am unable to attach wireshark pcap files due to privacy constraints. Thanks for any help.