This would have to be accompanied by new regulations on derivatives and dark pools, but on the surface it doesn't seem like a bad idea.
Currently, all major banks have:
1) Shadow markets setup (dark pools) to allow big investors to take positions without anyone knowing.
2) Servers sitting beside the exchange that get to see all trades before the public does.
Neither of these things should be legal.
I don't know if I believe that high-frequency traders provide a necessary liquidity. I can see both sides on that, but I think we will never know until we impose a tax like Cuban is suggesting. If we don't like the results, we can always repeal the tax.