Have you tried changing your card via your computer's iTunes instead of on an iOS device (or on an iOS device if currently using an iOS device) ?
For a card to have a change of being accepted by iTunes it needs to be registered to the same name and address (including layout and spacing) as on the iTunes account, and have been issued by a bank in the country where you are (and which is therefore the country on the account). Prepaid cards are unlikely to be accepted, and not all debit cards seem to work with iTunes. If you want to contact iTunes Support about it use the 'contact Support' link at the top right of every page on here