I'm here to answer questions if there are any (I run Bitbucket.)
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.