I have searched for debit cards before because I wanted to be able to drop my credit and debit cards and have an easy way to budget out my spending for the month.
What I found were a huge amount of fees. Fees such as $9.95 activation fee, $4.95 per month fee, a non-activity fee, 50 cents per purchase, one company requires a $99 activation fee.
A good service to compete with this may be a debit account that can be used to pay for things in Bitcoins. There would still need to be a fee for converting your dollars to Bitcoins, but the debit company can get the fees down to around .25% per transaction with high volume on MtGox which would come out to a fee of 25 cents per $100 spent.
So you could set up your debit account, keep your cash in there for spending. When you go to buy something in Bitcoins it converts cash at the current rate into Bitcoins and pays for the product.
So where is the profit for the company? You have a bunch of cash from customers, you put that in an account and collect interest or do the fiat thing and make money the same way that banks make money on deposited money. You might even be able to lower the .25% per transaction cost for those who have higher balances or even just do a (no transaction fee for accounts with more than $500). So there would be no fee.
Just a thought. I know that this actually is counter to what Bitcoin is all about because we want to encourage people to convert their currency to BTC and use it, but this would be providing a cheaper service than banks can offer and encourage Bitcoin merchants to be set up.