I now found the reason, and it perfectly makes sense (took me a while to realize though, being a first time AWS user).
My instance is running on an SSD (more specifically, the volume type is called
gp2), but of course I have to share the hardware with a lot of other users, so Amazon limits the IOPS. Currently you get 3 IOPS per GB as baseline performance (but at least 100 IOPS for small volumes), and you're allowed to burst up to 3000 IOPS as long as you have what they call credits. Initially you get 5.4 million credits, which allows you to burst at 3000 IOPS for 30 minutes. After that you fall back to baseline performance, and during times when you don't use the volume your credits are filled up again at the baseline rate. More details here: Amazon EBS volume types
This matches the behaviour that I observed: Synching started out quite fast, but became incredibly slow later. Based on the above, it must have slowed down after around 30 minutes, which wasn't enough to sync the whole blockchain from scratch. Hence, when running on such an instance, it might make sense to download the blockchain from the monero website.