Did you reserve your instances? Were you using current generation instances (c3, m3, etc). Did you try to take advantage of traffic patterns to scale up and down the number of instances you were running?
It is like many other things involved in running a technology company. Investing in automation can pay off hugely.
The newer instance types are very reliable too (in my experience).