Hi I'll try backporting the Natty openssl package and see how it goes.

Not using a wildcard cert, although I have tested with one, as well as two seperate certs.

I have plenty of Apache debug logs, I'll distill some and upload when I have a moment Here's an ssldump that accompanied the s_client output above:

7 1  0.3464 (0.3464)  C>S SSLv2 compatible client hello
  Version 3.1 
  cipher suites
  Unknown value 0x39  
  Unknown value 0x38  
  Unknown value 0x35  
  TLS_DHE_RSA_WITH_3DES_EDE_CBC_SHA  
  TLS_DHE_DSS_WITH_3DES_EDE_CBC_SHA  
  TLS_RSA_WITH_3DES_EDE_CBC_SHA  
  SSL2_CK_3DES  
  Unknown value 0x33  
  Unknown value 0x32  
  Unknown value 0x2f  
  SSL2_CK_RC2  
  TLS_RSA_WITH_RC4_128_SHA  
  TLS_RSA_WITH_RC4_128_MD5  
  SSL2_CK_RC4  
  TLS_DHE_RSA_WITH_DES_CBC_SHA  
  TLS_DHE_DSS_WITH_DES_CBC_SHA  
  TLS_RSA_WITH_DES_CBC_SHA  
  SSL2_CK_DES  
  TLS_DHE_RSA_EXPORT_WITH_DES40_CBC_SHA  
  TLS_DHE_DSS_EXPORT_WITH_DES40_CBC_SHA  
  TLS_RSA_EXPORT_WITH_DES40_CBC_SHA  
  TLS_RSA_EXPORT_WITH_RC2_CBC_40_MD5  
  SSL2_CK_RC2_EXPORT40  
  TLS_RSA_EXPORT_WITH_RC4_40_MD5  
  SSL2_CK_RC4_EXPORT40  
  Unknown value 0xff  
7 2  0.3557 (0.0093)  S>CV3.1(81)  Handshake
      ServerHello
        Version 3.1 
        random[32]=
          4d f1 5f 69 e8 65 f9 9e 0e 21 fd f8 6e 05 11 bb 
          45 6b b8 97 49 62 04 68 60 a2 4a 94 11 4a 81 84 
        session_id[32]=
          c0 ca 5b 73 a3 9a 33 0a 65 30 8f 28 c2 db d1 d6 
          47 ff b6 0c bf 48 0f dd 1e 95 33 9b 56 8b 04 3e 
        cipherSuite         Unknown value 0x39
        compressionMethod                   NULL
7 3  0.3557 (0.0000)  S>CV3.1(3382)  Handshake
      Certificate
7 4  0.3557 (0.0000)  S>CV3.1(525)  Handshake
      ServerKeyExchange
7 5  0.3557 (0.0000)  S>CV3.1(4)  Handshake
      ServerHelloDone
7 6  0.7052 (0.3494)  C>SV3.1(2)  Alert
    level           fatal
    value           decrypt_error
7    0.7054 (0.0002)  S>C  TCP FIN
7    0.7066 (0.0012)  C>S  TCP RST

For comparison, here's the ssldump of the prior, successful connection:

6 1  0.3416 (0.3416)  C>S SSLv2 compatible client hello
  Version 3.1 
  cipher suites
  Unknown value 0x39  
  Unknown value 0x38  
  Unknown value 0x35  
  TLS_DHE_RSA_WITH_3DES_EDE_CBC_SHA  
  TLS_DHE_DSS_WITH_3DES_EDE_CBC_SHA  
  TLS_RSA_WITH_3DES_EDE_CBC_SHA  
  SSL2_CK_3DES  
  Unknown value 0x33  
  Unknown value 0x32  
  Unknown value 0x2f  
  SSL2_CK_RC2  
  TLS_RSA_WITH_RC4_128_SHA  
  TLS_RSA_WITH_RC4_128_MD5  
  SSL2_CK_RC4  
  TLS_DHE_RSA_WITH_DES_CBC_SHA  
  TLS_DHE_DSS_WITH_DES_CBC_SHA  
  TLS_RSA_WITH_DES_CBC_SHA  
  SSL2_CK_DES  
  TLS_DHE_RSA_EXPORT_WITH_DES40_CBC_SHA  
  TLS_DHE_DSS_EXPORT_WITH_DES40_CBC_SHA  
  TLS_RSA_EXPORT_WITH_DES40_CBC_SHA  
  TLS_RSA_EXPORT_WITH_RC2_CBC_40_MD5  
  SSL2_CK_RC2_EXPORT40  
  TLS_RSA_EXPORT_WITH_RC4_40_MD5  
  SSL2_CK_RC4_EXPORT40  
  Unknown value 0xff  
6 2  0.3512 (0.0095)  S>CV3.1(81)  Handshake
      ServerHello
        Version 3.1 
        random[32]=
          4d f1 5f 5c 41 3e 94 a9 68 9d 48 73 90 29 b2 08 
          62 b4 b6 6a 6b 98 ac 81 70 7d 44 a7 0c 6d fe ef 
        session_id[32]=
          dd 42 bf a7 3b 46 a0 eb 38 19 a0 bf 56 c1 22 17 
          1c aa b4 0c 97 79 ea b7 90 d1 78 f8 85 7c 00 c0 
        cipherSuite         Unknown value 0x39
        compressionMethod                   NULL
6 3  0.3512 (0.0000)  S>CV3.1(3382)  Handshake
      Certificate
6 4  0.3512 (0.0000)  S>CV3.1(525)  Handshake
      ServerKeyExchange
6 5  0.3512 (0.0000)  S>CV3.1(4)  Handshake
      ServerHelloDone
6 6  0.7370 (0.3858)  C>SV3.1(134)  Handshake
      ClientKeyExchange
6 7  0.7370 (0.0000)  C>SV3.1(1)  ChangeCipherSpec
6 8  0.7370 (0.0000)  C>SV3.1(48)  Handshake
6 9  0.7403 (0.0032)  S>CV3.1(1)  ChangeCipherSpec
6 10 0.7403 (0.0000)  S>CV3.1(48)  Handshake
6 11 10.9898 (10.2495)  S>CV3.1(32)  Alert
6    10.9899 (0.0000)  S>C  TCP FIN
6 12 11.3304 (0.3404)  C>SV3.1(32)  Alert
6    11.3314 (0.0010)  C>S  TCP FIN