They actually do. The question is: how far below 0 can they go.
A checking account with a $10,000 balance and $10 monthly fee actually produces a negative -1.2% yearly interest. If instead the balance was $100, at the end of the year, you've lost more than the principal: you'd be better off putting your money into the riskiest types of investment available on earth..
Of course, banks incur cost to deliver services and the client must pay. It impacts poor people much more than the wealthy. When you see transactions at ATM machines for instance, it is surprising to see the large number of people withdrawing $20 and paying $4 transaction fees. So, many people are already used to terrible interest rates - they just don't know it's a disguised interest.
But how far could bank go? In the above example (-1.2% interest rate) most people still keep their money in the bank for convenience reasons, particularly if there is no inflation. At -2% more people are going to just remove all their money and not have bank accounts anymore. At -10%, banks would no longer exist.
Also, the most negative interest rates impact the poorest / most risquier clients - clients that bank would be happy to get rid of if they could. These clients, despite all the fees they pay to the bank, are nevertheless unprofitable. People with lot's of money on their bank accounts usually don't have negative interest, after factoring out all fees.