Would you be willing to answer a few brief questions about PlayStation Forums?
The issue was with the verification (AVS/CVV2). See the following website link to see what information is verified for your card and focus only on entering the necessary info to get a "Match".
One caveat is that for the "street address" you may need to just enter the street number, i.e.
If you live at
5431 First St. Apt 101
Try just entering
Hope that helps someone!