It was fixed around 4am (GMT+2) last night, with the assistance of Amazon. I'm just going to summarize what happened here:

We were attacked. Massive UDP DDOS. The flood of traffic prevented us from accessing our EBS store with any acceptable speeds, which is what caused everyone to think the problem was between our EC2 and the EBS. Of course this also explains why booting up a new instance and EBS didn't help anything.

Also, it's happening again now, and we're working with Amazon to remedy it once more.