S3 should work too? Unless it was a global EBS failure, you should be able to restore from any backup to a new set of instances and stores, why doesn't that work?
As I said, our data is not lost, we have snapshots and backups, it's sitting right there on the mount, we're just not getting any sort of acceptable throughput. New instances does not fix the problem.
Ironically, we were looking into having S3 as the backend for our data, for scalability/redundancy purposes, but this pretty much puts a stop to that.
Yes, we did try this, and it produced the same problem.