I've been having this issue for a week. I have a new credit card and all I got was a vague error. I chatted with support, I talked to support on the phone and they went through the troubleshooting with me and after we tried everything they told me to buy a PSN card or use paypal (I'm not blaming them, they're doing what they've been trained to and they were very polite). For the heck of it, I tried putting a space at then end of my city's name. And, voila, it's working now. I hope this works for someone else.
I had the same massage when wanted to add new purchased psn$50 code, I just contacted chat and we found out that retailer did not activated card correctly, so I have been replaced with new card/code.
I can't even access the PlayStation Store, no idea what is going on. Maybe an update, hopefully. By the way, it is showing the same error.