Unfortunately, though, plain DHE is really slow, so it's pretty hardware-intensive to do it at scale, and to keep latency manageable. Google made a big deal out of moving to ECDHE the year before last, and part of that was that it allowed them to get perfect forward secrecy without sacrificing performance.
We just went through some similar stuff, having to ditch Amazon Linux for our SSL termination machine because Red Hat strips out all elliptic-curve crypto. It might also be worth investigating whether or not the Debian 7 OpenSSL build includes the optimized 64-bit ECDHE implementation contributed by Google, which wasn't enabled in Ubuntu's build until last month.
