You used the card through PayPal I'm assuming. Is your account verified? Occasionally that can cause a lot of issues. I had the same issue when purchasing things off of iTunes via PayPal and a Visa giftcard. Vanilla Gift or some other version of the card?