The 'charges' are temporary : iTunes Store & Mac App Store: About payment card authorization holds.
For the 'declined' message, debit cards don't appear to still be accepted in all countries, and even where they are it seems (based on posts on here) that not all accepted.
For a card to have a chance of being accepted it needs to be registered to exactly the same name and address (including format and spacing etc) that you have on your iTunes account, and have been issued by a bank in the country where you and your iTunes account are. If it is then you could check with the card issuer to see if it's them that are declining it, and if not then try contacting iTunes Support (these are user-to-user forums) and see if they know why it's being declined (but you might not be able to use a debit card) : http://www.apple.com/support/itunes/contact/ - click on Contact iTunes Store Support on the right-hand side of the page, then Purchases, Billing & Redemption
Or if you have a different card then you could see if that one works that instead.