Wow, those are some large numbers. 500m requests received and ~300k visits. 500m/330k ~ 1.6k requests per visit. He is right that 500m requests via AWS cloudfront (even S3) would cost around $500-600 [1]. With so many requests you get dinged pretty hard. The main issue was probably bandwidth saturation. Good job, it was fun to explore the map!
[1] http://calculator.s3.amazonaws.com/calc5.html