Desde la última semana de Agosto muchos clientes de iTunes USA que usan la tienda con tarjeta de crédito o con PayPal han visto este mensaje de error una y otra vez salir, sin poder comprar nada ni actualizar sus Apps.
Your credit card was declined. Please enter valid credit card information.
Cuando intentas comprar algo (una app o una canción) luego de hacer login con tu cuenta, te sale una nueva ventana que indica:
Verification is required
You must enter your Apple ID and password, click Billing Info, and verify your payment information in order to make purchases.
Y una vez que vuelves a loguearte con eso para verificar tus datos de pago, te sale un formulario con letras rojas que indican:
You must verify your payment information before you can make purchases.
Aunque vuelvas a poner tus datos, ya sean de PayPal o de tu tarjeta de crédito, y aprietas Done, te da nuevamente error:
Your credit card was declined. Please enter valid credit card information
Osea que tu tarjeta de crédito fue rechazada y que ingreses valores válidos al respecto. Y esto se convierte en un LOOP infinito en el que Apple nunca volverá a aceptar tus datos ni el de otras tarjetas, por más válidas que estén.
Motivos
Hay una teoría: Leyendo foros al respecto, la mayoría de estos errores suceden si tu IP esta fuera de USA, es decir que por más que uses un Paypal o una tarjeta de crédito de Estados Unidos, si no te encuentras en el mismo país, te saldrá este error.
Algunas personas reportaron que al estar en otro país les da este error, pero cuando llamaron a un pariente en USA, para que intente loguearse con la misma cuenta y comprar algo, el error no existía.
Pero a su vez unos pocos afectados indican que si se encuentran en USA y aún así les sale este error. 
Soluciones
Es un error de iTunes Store, no es ni de tu banco ni de PayPal. Aún no hay soluciones aparentes. Recomiendo que leas estos 3 foros de Apple Support y si estas pasando por este mismo problema veas también de dejar un comentario para que Apple se de cuneta que son muchos los perjudicados, aunque ya de entrada parece SI SON BASTANTES. Estos son los posts:
- Topic: Credit Card is Declined
- Topic: Your payment method was declined
- Topic: Credit card verification loop
Como verás no es un error aislado que le esta pasando a pocos.
Muchos indican que la única solución es enviar un email a Apple Support a este enlace y esperar 48 horas a una respuesta:
Apple Support, iTunes Store: Billing, managing your account
Esperemos que pronto haya una solución.
Si pasaste por algo similar y lo solucionaste, no dudes en dejar un comentario 
Se solucionó mi caso
La única solución es ponerse en contacto con Apple Support usando el fomrulario ya mencionado. El miércoles envié mi primera queja por esta falla, me dijeron que tan pronto verían y revisarían mi cuenta se comunicarían conmigo, sin otra noticia adicional estuvieron varios días callados. El Viernes envié un segundo mensaje y hoy Sábado 4 de Septiembre, luego de 4 días, me enviaron un email indicando que ya arreglaron mi cuenta y que verifique todos mis datos. Ya todo se solucionó y ya puedo comprar normal nuevamente.