I had this problem as well and after some searching found that I was not alone. Unfortunately I also could not find an immediate solution. I did find a way around it though! Simply create a new apple id ( which you can do through apple's website here:
https://appleid.apple.com/cgi-bin/WebObjects/MyAppleId.woa/228/wa/createAppleId? wosid=qjNCb5TQ9sf7hhd85ggabg&localang=en_US
After you've created a new ID, go to your phone enter into settings > store and tap on your current apple ID. It will open a prompt where you can sign out. Sign in again with your new ID and you're set! It's a hassle mostly because you'll need to open a new e-mail account... But most people already have 2 or 3 anyway. All you have to do now is enter payment info for you're new ID. Don't worry it will bring up a promt for this the first time you try to purchase something through the app store or iTunes.
This worked for me... Though its annoying and time consuming it's not as bad as not being able to purchase what you want on your phone. Hope this helped!! :D
Just as a side note I also tried checking billing information etc. and tried changing cards... None of which worked. This is the only solution I found. I did read that someone else had problems after their card expired. This is when my problem began as well so maybe there is a bug in the system relating to the expiration of credit/debit cards. I don't think that apple doesn't accept debit though... My card is a visa debit and I had no problems until it expired.