First, let's just agree that supporting SSLv3 is no longer a good idea, and that all old versions of SSL should be disabled by default. In fact, if I could add one item to the Top 10 Hardcore Securi...
Jonathan, take another look at the updated cipher string in the article above, which moves ECDHE to the front of the order, ahead of DHE. That should solve your primary problem.