http://dl.dropbox.com/u/24257718/cipher_chart.png
Virtually all server side hardware can do AES-NI instructions in hardware now (unless you are using ATOM cpu for ssl connections?) and most non-mobile hardware clients can do AESNI too for AES-128
The problem is that the widely-deployed AES ciphersuite, like the ciphersuites for triple DES and IDEA, uses a construction from the '90s that is itself insecure. It's based on CBC mode (which is fine) in a MAC-then-encrypt configuration (which is not), which lead to the Lucky 13 attack, and which until TLS 1.1 didn't properly set up the IVs for each record, which lead to BEAST.
No major site used RC4 because it was more performant. They used it as a workaround to Lucky 13 and BEAST, because they couldn't count on browsers fixing those problems fast enough.
[1] http://security.stackexchange.com/questions/17080/is-there-a...
Try the https://www.ssllabs.com/ssltest/index.html scan and you'll see what it thinks of your SSL setup. With BEAST vulnerability you get non compliance.
That tool you posted is great, hugely helpful for anyone who has to deal with this stuff.
ECDHE-RSA-AES128-SHA256:AES128-GCM-SHA256:RC4:HIGH:!MD5:!aNULL:!EDH(The idea behind the config above is to propose TLS 1.2 ciphersuites, which aren't susceptible to BEAST, and leave RC4 as a fallback for older TLS implementations. But TLS 1.2 support in browsers is still problematic.)
Also, ECDHE-RSA-AES128-SHA256 is still decrypt-then-verify CBC mode, isn't it? GCM should be listed first.
Upgrading takes time.