Ok, given that I discovered the same behavior from wget I decided going directly to openssl.

root@natty:~# openssl s_client -connect www.etisalat.com.eg:443
CONNECTED(00000003)
1432:error:140773F2:SSL routines:SSL23_GET_SERVER_HELLO:sslv3 alert unexpected message:s23_clnt.c:602:
root@natty:~#

Looks familiar?

Explicitly asking for ssl3, we get the following response:

root@natty:~# openssl s_client -ssl3 -connect www.etisalat.com.eg:443
CONNECTED(00000003)
depth=3 /C=US/O=GTE Corporation/OU=GTE CyberTrust Solutions, Inc./CN=GTE CyberTrust Global Root
verify error:num=19:self signed certificate in certificate chain
verify return:0
---
Certificate chain
 0 s:/C=EG/L=Cairo/ST=Cairo/O=etisalat/OU=IT/CN=*.etisalat.com.eg
   i:/C=AE/O=Etisalat/OU=Etisalat eBusiness Services/CN=Comtrust Server Certification Authority
 1 s:/C=AE/O=Etisalat/OU=Etisalat eBusiness Services/CN=Comtrust Server Certification Authority
   i:/C=AE/O=Etisalat/OU=Etisalat eBusiness Services/CN=Comtrust Root Certification Authority
 2 s:/C=AE/O=Etisalat/OU=Etisalat eBusiness Services/CN=Comtrust Root Certification Authority
   i:/C=US/O=GTE Corporation/OU=GTE CyberTrust Solutions, Inc./CN=GTE CyberTrust Global Root
 3 s:/C=US/O=GTE Corporation/OU=GTE CyberTrust Solutions, Inc./CN=GTE CyberTrust Global Root
   i:/C=US/O=GTE Corporation/OU=GTE CyberTrust Solutions, Inc./CN=GTE CyberTrust Global Root
---
Server certificate
-----BEGIN CERTIFICATE-----
MIID5TCCAs2gAwIBAgICEEswDQYJKoZIhvcNAQEFBQAweDELMAkGA1UEBhMCQUUx
ETAPBgNVBAoTCEV0aXNhbGF0MSQwIgYDVQQLExtFdGlzYWxhdCBlQnVzaW5lc3Mg
U2VydmljZXMxMDAuBgNVBAMTJ0NvbXRydXN0IFNlcnZlciBDZXJ0aWZpY2F0aW9u
IEF1dGhvcml0eTAeFw0xMDAzMTQxMzM5MThaFw0xMjAzMTQxMzM5MThaMGkxCzAJ
BgNVBAYTAkVHMQ4wDAYDVQQHEwVDYWlybzEOMAwGA1UECBMFQ2Fpcm8xETAPBgNV
BAoTCGV0aXNhbGF0MQswCQYDVQQLEwJJVDEaMBgGA1UEAxQRKi5ldGlzYWxhdC5j
b20uZWcwgZ8wDQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAMtR6BtuLt3MYE91KI0Q
ZgYUK7Qd+xb+8noqbRMnA2fWRML5slebffXjR6/MnTKd3mg4kh8+N1CYdWnnuQXq
AsY/jcgZ7aH3lPga1BeVXCbAARJfVUy4XXIh60kCg1pibz2ZdM6y/qXHccLjDwet
I7IiLUGsqYjBGv/I2DEWt1ZrAgMBAAGjggEKMIIBBjAJBgNVHRMEAjAAMEwGA1Ud
IARFMEMwQQYLKwYBBAGyXQIBAQAwMjAwBggrBgEFBQcCARYkaHR0cDovL2NvbXRy
dXN0LmV0aXNhbGF0LmFlL2Nwcy5odG1sMCYGA1UdEQQfMB2BG1RhbWVyLkVsR29o
YXJ5QGV0aXNhbGF0LmNvbTAOBgNVHQ8BAf8EBAMCBaAwEwYDVR0lBAwwCgYIKwYB
BQUHAwEwHwYDVR0jBBgwFoAUeIDkXQxvf3/oqMvK+Q5xYj6rQrowPQYDVR0fBDYw
NDAyoDCgLoYsaHR0cDovL2NvbXRydXN0LmV0aXNhbGF0LmFlL2NybC9zZXJ2ZXJj
YS5jcmwwDQYJKoZIhvcNAQEFBQADggEBAI9mNP5zkEKRuG9DO4HDPCVNsTVmrMnt
oTK1vnzFGKAXamb87jy35yADNOYcFOH4VXOaEjtJOy9s3UUtd/A80JYw2zjyEzud
9kTdefiXBOd8pescZa8f7xzy5UPBacWBu1hxAAF0Pj8uL5QYULZmL50G4DINsDUi
DjyGAWJDyotGRqbFKX7XhJb+t793a1hvdvGFfW+QI4ovHTh8D+RK+i+/g/8oE/a4
JE3e2E+Pj7FzqrDTurkq6w0tj/24YLepudo936NpAfC7RtjxPSb647+2Tdjf4Kao
z0hjMrS30cnTjQMNw+QqQmNrNp21rKM7QHCmCnYEAWn0TkGMx5enNEA=
-----END CERTIFICATE-----
subject=/C=EG/L=Cairo/ST=Cairo/O=etisalat/OU=IT/CN=*.etisalat.com.eg
issuer=/C=AE/O=Etisalat/OU=Etisalat eBusiness Services/CN=Comtrust Server Certification Authority
---
No client certificate CA names sent
---
SSL handshake has read 3996 bytes and written 301 bytes
---
New, TLSv1/SSLv3, Cipher is DES-CBC3-SHA
Server public key is 1024 bit
Secure Renegotiation IS NOT supported
Compression: NONE
Expansion: NONE
SSL-Session:
    Protocol  : SSLv3
    Cipher    : DES-CBC3-SHA
    Session-ID: 
    Session-ID-ctx: 
    Master-Key: 6AC3114D500CAC9F4A5135EDCFA45D905DF09FFECB10F818AF679B17062F0811F685DF6745C5B91A86D7DC3BA5770BC7
    Key-Arg   : None
    Start Time: 1290712758
    Timeout   : 7200 (sec)
    Verify return code: 19 (self signed certificate in certificate chain)
---

This using openssl 0.9.8o-1ubuntu4.2, which currently is what is in Natty.

To be honest I don't know enough about how ssl/tls is supposed to work to say whatever this is a bug in openssl or if it is due to some server side quirk.