Sometimes other servers are just slow. You can try to decompose what they're doing, and try to see if it's the network between you and the webservice.

And when you're dealing with databases, searches against some fields are faster than other fields. This doesn't surprise me at all.

It's also possible that you caught them at a degraded period of time. (I don't know their setup, but they might've broken a mirror, so they could back up from a consistent point in time). They could've also had a failure that they were in the process of recovering from.

A quick search on Amazon Web Service suggests that they made changes last week.