The problem seemed to be the lack of a billing address -- what are you supposed to put? Nothing worked. On another site that processed their credit cards via PayPal, it didn't work either. I called PayPal customer service and they explicitly told me they don't support cards that don't provide a means to verify a valid billing address and 3-digit security code.
Now, it's not like I don't have other identifiable information on my amazon account (a real credit card, a previously used shipping address, etc), so it's not anonymous, but they do accept prepaid cards.