Yes, the Wii U eShop does accept debit cards.
I am having the same issue as cheep-cheep.
I am in the US and I used my Visa debit card at a previous address. Then I moved, still in the US, changed my address with my bank, and changed my location in the Wii U eShop and on my user account with Nintendo, but the eShop says the addresses don't match.
It's definitely on the Nintendo side because my bank is approving all of the attempted transactions. They actually show up in my online statement as pending.
I suspect the issue is that the eShop only asks for a location, city, state and county, instead of an address. There are even locations that don't exist such as the area where I live. There is the actual location listed and also a local name for the area which is not real; similar to "China Town" in San Francisco.
I've called Nintendo multiple times to try and get this resolved, but no one there seems to understand how the system works.
I was given a supervisor's number, 877-803-3676, to call next but I have to wait for my tolerance level to build back up to tackle this again.
I'll post an update the next time I have a couple hours to waste on hold.