One is a choice the other is not.
While they are both liabilities on the balance sheet, in the real world they are quite different.
We do not feel as much ownership over our money that goes to interest payments as we do over our tax payments. Taxes pay for our government and the services it provides. Interest, on the other hand, is what we pay in order to have a bank loan us money. Similar to paying for a good or service obtained from some other business, we do not feel we have a say in what the bank does with that money. If we disapprove of a business' practices, we stop doing business with them; assuming there are other choices. We can not practically avoid dealing with our government.
We certainly feel that we should have a say in what is done with our tax money. I doubt there is anyone in the world that completely approves of their government's spending. It is very easy to feel marginalized with regard to our tax payments. For example, some people feel resentment because their taxes fund the welfare rolls.
All that said, I believe there is little overlap between the two groups. It seems to me that you are referring to those with large amounts of high interest (e.g. credit card) debt. I doubt that a large percentage of them are scouring the tax laws, looking for deductions and loopholes. If they had that mindset, they would also be working hard to get out of the hole they are in.
In summary, we choose to pay a financial adviser, to take out a loan or to obtain a credit card. We do not choose to pay taxes. Since taxes are supposed to pay for our government and things which should benefit everyone, we want a say in what is done with it. This is also the case because it is forced on us. ("Fine son, I'll lend you some money, but I don't want you buying cigarettes with it.") Since our say is limited and we likely will not approve of everything our government does, we want to exert what control we do have: reduce our payments as best we can.