Did the original AWS setup use Memcached? It doesn't sound like it, and clearly that would make a huge difference (and perhaps explain the sluggishness)?
In other words, they could have just added memcached to the AWS setup and gotten the same (or better) gains?